제출 #705381

#제출 시각아이디문제언어결과실행 시간메모리
705381LittleCubeTug of War (BOI15_tug)C++14
71 / 100
3024 ms14160 KiB
#pragma GCC optimize("Ofast,unroll-loops") #include <bits/stdc++.h> #define ll long long #define pii pair<int, int> #define pll pair<ll, ll> #define F first #define S second using namespace std; int n, k, pre[120005], vis[120005], match[120005], cnt; bitset<30000 * 20 * 4> b, bb; vector<pii> E[120005], T[120005]; pair<pii, int> nT; vector<int> cV; bool valid = 1; void dfs(int u) { cnt += (u <= 2 * n ? 1 : -1); cV.emplace_back(u); vis[u] = 1; for (auto [v, w] : E[u]) if (!vis[v]) { T[u].emplace_back(pii(v, w)); pre[v] = u; dfs(v); } else if (v != pre[u]) nT = make_pair(pii(u, v), w); } int matching(int u) { int tot = 0; for (auto [v, w] : T[u]) { tot += matching(v); if (!match[u] && !match[v]) match[u] = match[v] = 1, tot += w; } return tot; } signed main() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); cin >> n >> k; for (int i = 1; i <= 2 * n; i++) { int l, r, w; cin >> l >> r >> w; E[i].emplace_back(pii(2 * n + l, w)); E[2 * n + l].emplace_back(pii(i, w)); E[i].emplace_back(pii(3 * n + r, -w)); E[3 * n + r].emplace_back(pii(i, -w)); } b[40 * n + 1] = 1; for (int i = 1; i <= 2 * n; i++) if (!vis[i]) { cV.clear(); dfs(i); if (cnt != 0) { cout << "NO\n"; cerr << "there is no perfect matching (vertex)\n"; return 0; } vector<int> sol; bool mvalid = 1; int res = matching(i); for (auto j : cV) { mvalid &= match[j]; match[j] = 0; } if (mvalid) sol.emplace_back(res); match[nT.F.F] = match[nT.F.S] = 1; mvalid = 1; res = nT.S + matching(i); for (auto j : cV) mvalid &= match[j]; if (mvalid) sol.emplace_back(res); if (sol.size() == 0) { cout << "NO\n"; cerr << "there is no perfect matching (dfs)\n"; return 0; } bb = 0; for (auto j : sol) { if (j < 0) bb = bb | b >> (-j); else bb = bb | b << j; } b = bb; } for (int i = 40 * n + 1 - k; i <= 40 * n + 1 + k; i++) if (b[i]) { cout << "YES\n"; return 0; } cout << "NO\n"; cerr << "k is too small\n"; }

컴파일 시 표준 에러 (stderr) 메시지

tug.cpp: In function 'void dfs(int)':
tug.cpp:22:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   22 |     for (auto [v, w] : E[u])
      |               ^
tug.cpp: In function 'int matching(int)':
tug.cpp:36:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   36 |     for (auto [v, w] : T[u])
      |               ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...