Submission #681964

#TimeUsernameProblemLanguageResultExecution timeMemory
681964MilosMilutinovicTug of War (BOI15_tug)C++14
Compilation error
0 ms0 KiB
#include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <cmath> #include <vector> #include <set> #include <map> #include <unordered_set> #include <unordered_map> #include <queue> #include <ctime> #include <cassert> #include <complex> #include <string> #include <cstring> #include <chrono> #include <random> #include <bitset> #include <array> using namespace std; typedef long long ll; const int N = 60666; int n, k; int l[2 * N]; int r[2 * N]; int s[2 * N]; vector<int> g[4 * N]; int ver; int pos; bool was[4 * N]; ll sum[2]; vector<int> comp; bool have[4 * N]; bool taken[4 * N]; bitset<40 * N + 1> dp; void addEdge(int v, int u) { g[v].push_back(u); g[u].push_back(v); } void dfs(int v) { if (v < 2 * n) { sum[ver & 1] += s[v]; ver++; } else pos++; was[v] = true; comp.push_back(v); for (int u : g[v]) if (!was[u]) dfs(u); } bool OK; void Go(int p) { taken[p] = true; for (int x : g[p]) { if (!have[x]) { assert((p == 2 * n + l[x]) || (p == (3 * n + r[x]))); int w = (p ^ (2 * n + l[x]) ^ (3 * n + r[x])); if (taken[w]) OK = false; else { sum[(w < 3 * n)] += s[x]; taken[w] = true; have[x] = true; Go(w); } } } } bool Try(int i, int p) { OK = true; for (int it : comp) { have[it] = false; taken[it] = false; } sum[0] = 0; sum[1] = 0; sum[(p < 3 * n)] += s[i]; have[i] = true; Go(p); return OK; } int main() { // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); scanf("%d%d", &n, &k); assert(k >= 0); for (int i = 0; i < 2 * n; i++) { scanf("%d%d%d", &l[i], &r[i], &s[i]); --l[i];--r[i]; addEdge(i, 2 * n + l[i]); addEdge(i, 3 * n + r[i]); } vector<pair<int, int>> canSame; vector<int> mustDiff; for (int i = 0; i < 2 * n; i++) if (!was[i]) { ver = 0; pos = 0; sum[0] = 0; sum[1] = 0; comp.clear(); dfs(i); if (ver > pos) { printf("NO\n"); return 0; } assert(Try(i, 3 * n + r[i]) || Try(i, 2 * n + l[i])); if (!Try(i, 3 * n + r[i])) { assert(Try(i, 2 * n + l[i])); mustDiff.push_back(sum[0] - sum[1]); } else if (!Try(i, 2 * n + l[i])) { assert(Try(i, 3 * n + r[i])); mustDiff.push_back(sum[0] - sum[1]); } else { assert(Try(i, 2 * n + l[i])); int S00 = sum[0]; int S01 = sum[1]; assert(Try(i, 3 * n + r[i])) int S10 = sum[0]; int S11 = sum[1]; canSame.push_back({S00 - S01, S10 - S11}); } } dp[20 * N] = 1; for (auto x : canSame) { int a = x.first; int b = x.second; if (a >= 0 && b >= 0) { dp = ((dp << a) | (dp << b)); } else if (a < 0 && b >= 0) { dp = ((dp >> (-a)) | (dp << b)); } else if (a >= 0 && b < 0) { dp = ((dp << a) | (dp >> (-b))); } else { dp = ((dp >> (-a)) | (dp >> (-b))); } } for (int x : mustDiff) { if (x < 0) dp = (dp >> (-x)); else dp = (dp << x); } bool ok = false; for (int i = 0; i <= k; i++) if (dp[20 * N + i] || dp[20 * N - i]) ok = true; if (ok) printf("YES\n"); else printf("NO\n"); return 0; }

Compilation message (stderr)

tug.cpp: In function 'int main()':
tug.cpp:128:4: error: expected ';' before 'int'
  128 |    int S10 = sum[0];
      |    ^~~
tug.cpp:130:34: error: 'S10' was not declared in this scope; did you mean 'S11'?
  130 |    canSame.push_back({S00 - S01, S10 - S11});
      |                                  ^~~
      |                                  S11
tug.cpp:130:44: error: no matching function for call to 'std::vector<std::pair<int, int> >::push_back(<brace-enclosed initializer list>)'
  130 |    canSame.push_back({S00 - S01, S10 - S11});
      |                                            ^
In file included from /usr/include/c++/10/vector:67,
                 from tug.cpp:6:
/usr/include/c++/10/bits/stl_vector.h:1187:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = std::pair<int, int>; _Alloc = std::allocator<std::pair<int, int> >; std::vector<_Tp, _Alloc>::value_type = std::pair<int, int>]'
 1187 |       push_back(const value_type& __x)
      |       ^~~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:1187:35: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const value_type&' {aka 'const std::pair<int, int>&'}
 1187 |       push_back(const value_type& __x)
      |                 ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_vector.h:1203:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(std::vector<_Tp, _Alloc>::value_type&&) [with _Tp = std::pair<int, int>; _Alloc = std::allocator<std::pair<int, int> >; std::vector<_Tp, _Alloc>::value_type = std::pair<int, int>]'
 1203 |       push_back(value_type&& __x)
      |       ^~~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:1203:30: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::vector<std::pair<int, int> >::value_type&&' {aka 'std::pair<int, int>&&'}
 1203 |       push_back(value_type&& __x)
      |                 ~~~~~~~~~~~~~^~~
tug.cpp:95:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |  scanf("%d%d", &n, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~
tug.cpp:98:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |   scanf("%d%d%d", &l[i], &r[i], &s[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~