제출 #79616

#제출 시각아이디문제언어결과실행 시간메모리
79616minhtung0404Tug of War (BOI15_tug)C++17
71 / 100
928 ms3652 KiB
//https://oj.uz/problem/view/BOI15_tug #include<bits/stdc++.h> const int N = 30005; using namespace std; typedef pair <int, int> ii; vector <ii> adj[N]; vector <int> mv; int n, k, cnt[2*N], d[2*N], C[2], sum; bool dead[2*N], dp[40*N]; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> k; for (int i = 1; i <= 2*n; i++){ int l, r, c; cin >> l >> r >> c; adj[l].push_back(ii(r+n, c)); cnt[l]++; adj[r+n].push_back(ii(l, c)); cnt[r+n]++; d[i] = -1; } queue <int> mq; for (int i = 1; i <= 2*n; i++) if (cnt[i] == 1) mq.push(i); while (mq.size()){ int u = mq.front(); mq.pop(); dead[u] = true; for (auto p : adj[u]){ if (dead[p.first]) continue; cnt[p.first]--; C[(u <= n)] += p.second; if (cnt[p.first] == 1) mq.push(p.first); } } for (int i = 1; i <= 2*n; i++) { if (!dead[i]) { if (cnt[i] != 2) return cout << "NO", 0; int u = i, num = 0, ck = 1; for (auto p : adj[u]){ int v = p.first, cost = p.second; if (dead[v]) continue; num = cost; } while (ck){ dead[u] = true; ck = 0; for (auto p : adj[u]){ int v = p.first, cost = p.second; if (dead[v]) continue; u = v; num = cost - num; ck = 1; break; } } mv.push_back(abs(num)); sum -= abs(num); } } for (int i = 0; i < 40*N; i++) dp[i] = 0; sort(mv.begin(), mv.end()); dp[0] = 1; int cnt = 0; for (; cnt < mv.size();) { int val = mv[cnt], num = 0; while (cnt < mv.size() && mv[cnt] == val) cnt++, num += val; for (int i = 0; i < val; i++){ int last = -1; for (int j = i; j < 40*N; j += val){ if (dp[j]) { last = j; } else { if (last != -1 && (j - last) <= num) dp[j] = 1; } } } } for (int i = 0; i < 40*N; i++){ if (abs(C[0] - C[1] + sum + i*2) <= k && dp[i]) return cout << "YES", 0; } cout << "NO"; }

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

tug.cpp: In function 'int main()':
tug.cpp:70:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (; cnt < mv.size();) {
            ~~~~^~~~~~~~~~~
tug.cpp:72:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (cnt < mv.size() && mv[cnt] == val) cnt++, num += val;
                ~~~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...