Submission #853666

#TimeUsernameProblemLanguageResultExecution timeMemory
853666NK_Tug of War (BOI15_tug)C++17
100 / 100
841 ms10144 KiB
// Success consists of going from failure to failure without loss of enthusiasm #include <bits/stdc++.h> using namespace std; #define nl '\n' #define pb push_back #define pf push_front #define mp make_pair #define f first #define s second #define sz(x) int(x.size()) template<class T> using V = vector<T>; using pi = pair<int, int>; using vi = V<int>; using vpi = V<pi>; using ll = long long; using pl = pair<ll, ll>; using vpl = V<pl>; using vl = V<ll>; using db = long double; template<class T> using pq = priority_queue<T, V<T>, greater<T>>; const int MOD = 1e9 + 7; const ll INFL = ll(1e17); const int LG = 18; const int nax = 3e4 + 10; const int kax = 20; const int SZ = nax * kax; const int Z = SZ / 2; using B = bitset<SZ>; int main() { cin.tie(0)->sync_with_stdio(0); int N, K; cin >> N >> K; int M = N; N += N; vi deg(N); vi W(N); V<set<pi>> adj(N); for(int i = 0; i < N; i++) { int u, v, w; cin >> u >> v >> w; --u, --v, v += M; W[i] = w; adj[u].insert(mp(v, i)); adj[v].insert(mp(u, i)); } queue<int> q; for(int i = 0; i < N; i++) { if (!sz(adj[i])) { cout << "NO" << nl; exit(0-0); } if (sz(adj[i]) == 1) q.push(i); } int BAL = 0; while(sz(q)) { int u = q.front(); q.pop(); pi e = *begin(adj[u]); adj[u].clear(); adj[e.f].erase(mp(u, e.s)); if (u < M) BAL += W[e.s]; else BAL -= W[e.s]; if (sz(adj[e.f]) == 1) q.push(e.f); } for(int i = 0; i < N; i++) { if (sz(adj[i]) == 0) continue; if (sz(adj[i]) != 2) { cout << "NO" << nl; exit(0-0); } } int bal = 0; function<void(int, int)> dfs = [&](int u, int d) { if (sz(adj[u])) { pi e = *begin(adj[u]); adj[u].clear(); adj[e.f].erase(mp(u, e.s)); // cout << u << " " << e.s << endl; bal += d * W[e.s]; dfs(e.f, -d); } }; vi X; for(int u = 0; u < M; u++) if (sz(adj[u])) { bal = 0; dfs(u, 1); X.pb(abs(bal)); } B dp; dp[Z + BAL] = 1; for(auto x : X) if (x) { dp = (dp << x) | (dp >> x); } for(int x = 0; x < SZ; x++) if (dp[x]) { // cout << x << endl; if (abs(x - Z) <= K) { cout << "YES" << nl; exit(0-0); } } cout << "NO" << nl; exit(0-0); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...