Submission #623706

#TimeUsernameProblemLanguageResultExecution timeMemory
623706JoshcTug of War (BOI15_tug)C++11
100 / 100
2153 ms10344 KiB
#include <bits/stdc++.h> using namespace std; #define pii pair<int, int> #define mp make_pair #define f first #define s second multiset<pii> edges[60005]; bitset<1200001> pos; int bal; void dfs(int x, int c) { if (!edges[x].empty()) { pii cur = *edges[x].begin(); edges[x].clear(); edges[cur.f].erase(edges[cur.f].find(mp(x, cur.s))); bal += c*cur.s; dfs(cur.f, -c); } } int main() { int n, k, x, y, z, balance = 600000; scanf("%d%d", &n, &k); for (int i=1; i<=2*n; i++) { scanf("%d%d%d", &x, &y, &z); y += n; edges[x].insert(mp(y, z)); edges[y].insert(mp(x, z)); } vector<int> forced; for (int i=1; i<=2*n; i++) { if (edges[i].empty()) { printf("NO\n"); return 0; } if (edges[i].size() == 1) forced.push_back(i); } while (!forced.empty()) { int cur = forced.back(); forced.pop_back(); pii x = *edges[cur].begin(); edges[cur].clear(); if (cur <= n) balance += x.s; else balance -= x.s; edges[x.f].erase(edges[x.f].find(mp(cur, x.s))); if (edges[x.f].size() == 1) forced.push_back(x.f); } pos.set(balance); for (int i=1; i<=2*n; i++) { if (!edges[i].empty()) { pii cur = *edges[i].begin(); edges[i].erase(edges[i].find(cur)); edges[cur.f].erase(edges[cur.f].find(mp(i, cur.s))); bal = cur.s; dfs(i, -1); //printf("Test: %d\n", bal); bal = abs(bal); pos = (pos << bal) | (pos >> bal); } } for (int i=-k; i<=k; i++) { if (0 <= 600000+i && 600000+i < 1200001 && pos[600000+i]) { printf("YES\n"); return 0; } } printf("NO\n"); }

Compilation message (stderr)

tug.cpp: In function 'int main()':
tug.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |     scanf("%d%d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~
tug.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |         scanf("%d%d%d", &x, &y, &z);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...