Submission #890899

#TimeUsernameProblemLanguageResultExecution timeMemory
890899nahco314Tug of War (BOI15_tug)C++14
23 / 100
60 ms4436 KiB
#include <bits/stdc++.h> using namespace std; #pragma GCC target("avx2") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") void ng() { cout << "NO" << endl; exit(0); } int remove(int v, vector<set<tuple<int, int, int>>>& g) { if (g[v].size() == 1) { tuple<int, int, int> elt = *g[v].begin(); int l = v; int r = get<0>(elt); int s = get<1>(elt); int i = get<2>(elt); g[l].erase({r, s, i}); g[r].erase({l, s, i}); return s + -remove(r, g); } return 0; } int dfs(int v, int used_e, int sign, vector<set<tuple<int, int, int>>>& g, vector<int>& seen) { seen[v] = sign; int res = 0; sign *= -1; for (auto [nxt, s, e] : g[v]) { if (e == used_e) continue; if (seen[nxt]) { if (seen[nxt] == sign) { continue; } else { ng(); } } res += sign * s; res += dfs(nxt, e, sign, g, seen); } // cerr << v << " " << used_e << " " << sign << " " << res << endl; return res; } int main() { int n, k; cin >> n >> k; vector<set<tuple<int, int, int>>> g(2 * n); for (int i = 0; i < 2 * n; i++) { int l, r, s; cin >> l >> r >> s; l--; r--; r += n; g[l].emplace(r, s, i); g[r].emplace(l, s, i); } int cur_sum = 0; for (int i = 0; i < 2 * n; i++) { int sign = i < n ? 1 : -1; cur_sum += remove(i, g) * sign; } vector<int> nums; vector<int> seen(2 * n, 0); for (int i = 0; i < 2 * n; i++) { if (seen[i]) continue; if (g[i].size() == 0) continue; int l = i; int r = get<0>(*g[i].begin()); int s = get<1>(*g[i].begin()); int used_e = get<2>(*g[i].begin()); int num = s + dfs(l, used_e, 1, g, seen); nums.push_back(num); } for (auto a : nums) { // cerr << "" << a << endl; } int m = nums.size(); int mid = n * 20 / 2; bitset<600001> cur(0); cur.set(cur_sum + mid); for (int i = 0; i < m; i++) { int num = abs(nums[i]); cur <<= num; cur |= cur >> (2 * num); /* cerr << i << endl; for (int i = 0; i < 600001; i++) { if (cur.test(i)) { cerr << i - mid << " "; } } cerr << endl; */ } for (int i = -k; i <= k; i++) { int num = mid + i; if (cur.test(num)) { cout << "YES" << endl; exit(0); } } cout << "NO" << endl; }

Compilation message (stderr)

tug.cpp: In function 'int dfs(int, int, int, std::vector<std::set<std::tuple<int, int, int> > >&, std::vector<int>&)':
tug.cpp:31:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   31 |     for (auto [nxt, s, e] : g[v]) {
      |               ^
tug.cpp: In function 'int main()':
tug.cpp:73:13: warning: unused variable 'r' [-Wunused-variable]
   73 |         int r = get<0>(*g[i].begin());
      |             ^
tug.cpp:81:15: warning: unused variable 'a' [-Wunused-variable]
   81 |     for (auto a : nums) {
      |               ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...