제출 #79792

#제출 시각아이디문제언어결과실행 시간메모리
79792VinhspmTug of War (BOI15_tug)C++14
0 / 100
48 ms36140 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back #define fi first #define se second typedef pair<int, int> ii; const int N = 4e5; const int M = 20 * 30000; const int oo = 1e9; ii a[N]; int n, maxn, sum, suma, cnt, curval, total; int cost[N], deg[N], f[350][40 * 30005]; bool alive[N], visit[N]; vector<int> vi[N]; map<int, int> val; void bad() { cout << "NO"; exit(0); } void upd(int &x, int y) { x = min(x, y); } void addeg(int u, int v) { deg[u] ++; deg[v] ++; vi[u].pb(v); vi[v].pb(u); } void kill(int u) { int u1 = 0, tmp = 0; for(int v: vi[u]) if(!alive[v]) { u1 = v; tmp ++; } if(tmp > 1) return; if(u <= 3*n) curval += cost[u1]; alive[u] = alive[u1] = 1; for(int v: vi[u1]) if(!alive[v]) kill(v); // :D } void check(int u) { visit[u] = true; int nex = -1; for(int v: vi[u]) if(!visit[v]) { nex = v; break; } if(nex == -1) bad(); visit[nex] = true; for(int v: vi[nex]) if(!visit[v]) check(v); return; // :D } void dfs(int u, bool spm) { if(spm == 0) suma += cost[u]; sum += cost[u]; alive[u] = true; int nex = -1; for(int v: vi[u]) if(!alive[v]) { nex = v; break; } alive[nex] = true; for(int v: vi[nex]) if(!alive[v]) dfs(v, 1 - spm); } signed main() { //freopen("test.inp", "r", stdin); ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); scanf("%d%d", &n, &maxn); for(int i = 1; i <= 2*n; ++i) { int l, r, c; scanf("%d%d%d", &l, &r, &c); total += c; addeg(i, 2*n + l); addeg(3*n + r, i); cost[i] = c; } for(int i = 2*n + 1; i <= 4*n; ++i) if(!visit[i] && deg[i] == 1) check(i); for(int i = 2*n + 1; i <= 4*n; ++i) if(!visit[i]) check(i); for(int i = 1; i <= 2*n; ++i) if(!visit[i]) bad(); for(int i = 2*n + 1; i <= 4*n; ++i) if(deg[i] == 1) kill(i); // now we have all the circle for(int i = 1; i <= 2*n; ++i) if(!alive[i]) { sum = suma = 0; dfs(i, 0); curval += min(suma, sum - suma); int x = max(suma, sum - suma) - min(suma, sum - suma); val[x] ++; } for(auto it = val.begin(); it != val.end(); ++it) a[++cnt] = ii(it->fi, it->se); // :D a[0].se = 0; //for(int i = 1; i <= n; ++i) cout << a[i].fi << ' ' << a[i].se << '\n'; //cout << curval << ' ' << total << '\n'; for(int i = 0; i <= cnt; ++i) for(int j = 0; j <= M; ++j) f[i][j] = oo; f[0][0] = 0; for(int i = 0; i <= cnt; ++i) for(int j = 0; j <= M; ++j) if(f[i][j] <= a[i].se) { if(f[i][j] < a[i].se) upd(f[i][j + a[i].fi], f[i][j] + 1); upd(f[i + 1][j], 0); } for(int i = 0; i <= M; ++i) if(f[cnt][i] <= a[cnt].se) { if(abs(2*(curval + i) - total) <= maxn) return cout << "YES", 0; } return cout << "NO", 0; }

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

tug.cpp: In function 'void check(int)':
tug.cpp:44:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
     if(nex == -1) bad(); visit[nex] = true;
     ^~
tug.cpp:44:26: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
     if(nex == -1) bad(); visit[nex] = true;
                          ^~~~~
tug.cpp: In function 'int main()':
tug.cpp:67:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &maxn);
  ~~~~~^~~~~~~~~~~~~~~~~~~
tug.cpp:69:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int l, r, c; scanf("%d%d%d", &l, &r, &c);
                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...