Submission #1840553


Source Code Expand

#include <bits/stdc++.h>
#include <sys/time.h>
using namespace std;

#define rep(i,n) for(long long i = 0; i < (long long)(n); i++)
#define repi(i,a,b) for(long long i = (long long)(a); i < (long long)(b); i++)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define mt make_tuple
#define mp make_pair
template<class T1, class T2> bool chmin(T1 &a, T2 b) { return b < a && (a = b, true); }
template<class T1, class T2> bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }

using ll = long long; using vll = vector<ll>; using vvll = vector<vll>; using P = pair<ll, ll>;
using ld = long double;  using vld = vector<ld>; 
using vi = vector<int>; using vvi = vector<vi>; vll conv(vi& v) { vll r(v.size()); rep(i, v.size()) r[i] = v[i]; return r; }

inline void input(int &v){ v=0;char c=0;int p=1; while(c<'0' || c>'9'){if(c=='-')p=-1;c=getchar();} while(c>='0' && c<='9'){v=(v<<3)+(v<<1)+c-'0';c=getchar();} v*=p; }
template <typename T, typename U> ostream &operator<<(ostream &o, const pair<T, U> &v) {  o << "(" << v.first << ", " << v.second << ")"; return o; }
template<size_t...> struct seq{}; template<size_t N, size_t... Is> struct gen_seq : gen_seq<N-1, N-1, Is...>{}; template<size_t... Is> struct gen_seq<0, Is...> : seq<Is...>{};
template<class Ch, class Tr, class Tuple, size_t... Is>
void print_tuple(basic_ostream<Ch,Tr>& os, Tuple const& t, seq<Is...>){ using s = int[]; (void)s{0, (void(os << (Is == 0? "" : ", ") << get<Is>(t)), 0)...}; }
template<class Ch, class Tr, class... Args> 
auto operator<<(basic_ostream<Ch, Tr>& os, tuple<Args...> const& t) -> basic_ostream<Ch, Tr>& { os << "("; print_tuple(os, t, gen_seq<sizeof...(Args)>()); return os << ")"; }
ostream &operator<<(ostream &o, const vvll &v) { rep(i, v.size()) { rep(j, v[i].size()) o << v[i][j] << " "; o << endl; } return o; }
template <typename T> ostream &operator<<(ostream &o, const vector<T> &v) { o << '['; rep(i, v.size()) o << v[i] << (i != v.size()-1 ? ", " : ""); o << "]";  return o; }
template <typename T> ostream &operator<<(ostream &o, const deque<T> &v) { o << '['; rep(i, v.size()) o << v[i] << (i != v.size()-1 ? ", " : ""); o << "]";  return o; }
template <typename T>  ostream &operator<<(ostream &o, const set<T> &m) { o << '['; for (auto it = m.begin(); it != m.end(); it++) o << *it << (next(it) != m.end() ? ", " : ""); o << "]";  return o; }
template <typename T>  ostream &operator<<(ostream &o, const unordered_set<T> &m) { o << '['; for (auto it = m.begin(); it != m.end(); it++) o << *it << (next(it) != m.end() ? ", " : ""); o << "]";  return o; }
template <typename T, typename U>  ostream &operator<<(ostream &o, const map<T, U> &m) { o << '['; for (auto it = m.begin(); it != m.end(); it++) o << *it << (next(it) != m.end() ? ", " : ""); o << "]";  return o; }
template <typename T, typename U, typename V>  ostream &operator<<(ostream &o, const unordered_map<T, U, V> &m) { o << '['; for (auto it = m.begin(); it != m.end(); it++) o << *it; o << "]";  return o; }
vector<int> range(const int x, const int y) { vector<int> v(y - x + 1); iota(v.begin(), v.end(), x); return v; }
template <typename T> istream& operator>>(istream& i, vector<T>& o) { rep(j, o.size()) i >> o[j]; return i;}
template <typename T, typename S, typename U> ostream &operator<<(ostream &o, const priority_queue<T, S, U> &v) { auto tmp = v; while (tmp.size()) { auto x = tmp.top(); tmp.pop(); o << x << " ";} return o; }
template <typename T> ostream &operator<<(ostream &o, const queue<T> &v) { auto tmp = v; while (tmp.size()) { auto x = tmp.front(); tmp.pop(); o << x << " ";} return o; }
template <typename T> ostream &operator<<(ostream &o, const stack<T> &v) { auto tmp = v; while (tmp.size()) { auto x = tmp.top(); tmp.pop(); o << x << " ";} return o; }
template <typename T> unordered_map<T, ll> counter(vector<T> vec){unordered_map<T, ll> ret; for (auto&& x : vec) ret[x]++; return ret;};
string substr(string s, P x) {return s.substr(x.fi, x.se - x.fi); }
void vizGraph(vvll& g, int mode = 0, string filename = "out.png") { ofstream ofs("./out.dot"); ofs << "digraph graph_name {" << endl; set<P> memo; rep(i, g.size())  rep(j, g[i].size()) { if (mode && (memo.count(P(i, g[i][j])) || memo.count(P(g[i][j], i)))) continue; memo.insert(P(i, g[i][j])); ofs << "    " << i << " -> " << g[i][j] << (mode ? " [arrowhead = none]" : "")<< endl;  } ofs << "}" << endl; ofs.close(); system(((string)"dot -T png out.dot >" + filename).c_str()); }
size_t random_seed; namespace std { using argument_type = P; template<> struct hash<argument_type> { size_t operator()(argument_type const& x) const { size_t seed = random_seed; seed ^= hash<ll>{}(x.fi); seed ^= (hash<ll>{}(x.se) << 1); return seed; } }; }; // hash for various class
struct timeval start; double sec() { struct timeval tv; gettimeofday(&tv, NULL); return (tv.tv_sec - start.tv_sec) + (tv.tv_usec - start.tv_usec) * 1e-6; }
struct init_{init_(){ ios::sync_with_stdio(false); cin.tie(0); gettimeofday(&start, NULL); struct timeval myTime; struct tm *time_st; gettimeofday(&myTime, NULL); time_st = localtime(&myTime.tv_sec); srand(myTime.tv_usec); random_seed = RAND_MAX / 2 + rand() / 2; }} init__;
uint32_t randxor() { static uint32_t x=1+(uint32_t)random_seed,y=362436069,z=521288629,w=88675123; uint32_t t; t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) ); }
#define rand randxor
#define ldout fixed << setprecision(40) 

#define EPS (double)1e-14
#define INF (ll)1e18
#define mo  (ll)(1e9+7)
ll n;
vvll g;
vll a;
vll dp;

ll dfs(ll v, ll p) {
    if (dp[v] != -1) return dp[v];
    if (g[v].size() == 1) return dp[v] = a[v];

    vll c;
    for (auto x : g[v]) if (x != p) {
        c.pb(dfs(x, v));
    }
    sort(all(c));
    ll cs = accumulate(all(c), 0ll);
    ll ret = 2ll * a[v] - cs;
    if (ret < 0 || a[v] > cs || a[v] < c.back()) { cout << "NO" << endl; exit(0); }
    dp[v] = ret;

    return ret;
}

int main(void) {
    cin >> n;
    a = vll(n); cin >> a;
    dp = vll(n, -1);
    g.resize(n);
    rep(i, n-1) {
        ll u, v; cin >> u >> v; u--, v--;
        g[u].pb(v); g[v].pb(u);
    }
    if (n == 2) {
        if (a[0] == a[1]) {
            cout <<"YES" << endl;
        } else {
            cout << "NO" << endl;
        }
        return 0;
    }

    rep(i, n) if (g[i].size() > 1) {
        dfs(1, -1);
        break;
    }
    cout << "YES" << endl;
    return 0;
}

Submission Info

Submission Time
Task C - Cleaning
User hamko
Language C++14 (GCC 5.4.1)
Score 0
Code Size 6510 Byte
Status WA
Exec Time 57 ms
Memory 16124 KB

Compile Error

./Main.cpp: In function ‘void vizGraph(vvll&, int, std::string)’:
./Main.cpp:41:478: warning: ignoring return value of ‘int system(const char*)’, declared with attribute warn_unused_result [-Wunused-result]
 void vizGraph(vvll& g, int mode = 0, string filename = "out.png") { ofstream ofs("./out.dot"); ofs << "digraph graph_name {" << endl; set<P> memo; rep(i, g.size())  rep(j, g[i].size()) { if (mode && (memo.count(P(i, g[i][j])) || memo.count(P(g[i][j], i)))) continue; memo.insert(P(i, g[i][j])); ofs << "    " << i << " -> " << g[i][j] << (mode ? " [arrowhead = none]" : "")<< endl;  } ofs << "}" << endl; ofs.close(); system(((string)"dot -T png out.dot >" + filename).c_str()); }
                                                                                                                                                                                                                                                                                                                                              ...

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 700
Status
AC × 2
WA × 1
AC × 39
WA × 12
Set Name Test Cases
Sample sample1.txt, sample2.txt, sample3.txt
All sample1.txt, sample2.txt, sample3.txt, in1.txt, in10.txt, in11.txt, in12.txt, in13.txt, in14.txt, in15.txt, in16.txt, in17.txt, in18.txt, in19.txt, in2.txt, in20.txt, in21.txt, in22.txt, in23.txt, in24.txt, in25.txt, in26.txt, in27.txt, in28.txt, in29.txt, in3.txt, in30.txt, in31.txt, in32.txt, in33.txt, in34.txt, in35.txt, in36.txt, in37.txt, in38.txt, in39.txt, in4.txt, in40.txt, in41.txt, in42.txt, in43.txt, in44.txt, in45.txt, in5.txt, in6.txt, in7.txt, in8.txt, in9.txt, sample1.txt, sample2.txt, sample3.txt
Case Name Status Exec Time Memory
in1.txt AC 51 ms 7932 KB
in10.txt AC 57 ms 7932 KB
in11.txt AC 56 ms 15612 KB
in12.txt AC 54 ms 15740 KB
in13.txt AC 49 ms 16124 KB
in14.txt AC 48 ms 13436 KB
in15.txt AC 1 ms 256 KB
in16.txt WA 1 ms 256 KB
in17.txt AC 1 ms 256 KB
in18.txt AC 1 ms 256 KB
in19.txt AC 51 ms 7932 KB
in2.txt AC 53 ms 7932 KB
in20.txt WA 41 ms 7932 KB
in21.txt WA 42 ms 7932 KB
in22.txt AC 51 ms 7932 KB
in23.txt WA 42 ms 7932 KB
in24.txt WA 41 ms 7932 KB
in25.txt AC 1 ms 256 KB
in26.txt WA 42 ms 7932 KB
in27.txt AC 42 ms 7932 KB
in28.txt WA 1 ms 256 KB
in29.txt AC 38 ms 7932 KB
in3.txt AC 52 ms 7932 KB
in30.txt AC 1 ms 256 KB
in31.txt AC 46 ms 7932 KB
in32.txt AC 43 ms 7932 KB
in33.txt AC 49 ms 7932 KB
in34.txt AC 51 ms 7932 KB
in35.txt AC 46 ms 7932 KB
in36.txt AC 42 ms 7932 KB
in37.txt AC 2 ms 380 KB
in38.txt WA 45 ms 7932 KB
in39.txt AC 44 ms 7932 KB
in4.txt AC 55 ms 7932 KB
in40.txt WA 40 ms 7932 KB
in41.txt AC 45 ms 7932 KB
in42.txt AC 52 ms 7932 KB
in43.txt AC 46 ms 7932 KB
in44.txt WA 40 ms 7932 KB
in45.txt AC 52 ms 7932 KB
in5.txt AC 40 ms 7932 KB
in6.txt AC 40 ms 7932 KB
in7.txt AC 36 ms 7164 KB
in8.txt AC 12 ms 2044 KB
in9.txt AC 41 ms 7932 KB
sample1.txt AC 1 ms 256 KB
sample2.txt WA 1 ms 256 KB
sample3.txt AC 1 ms 256 KB