Submission #84727

#TimeUsernameProblemLanguageResultExecution timeMemory
84727updown1Islands (IOI08_islands)C++17
80 / 100
1401 ms132096 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define For(i, a, b) for(int i=a; i<b; i++) #define ffi For(i, 0, N) #define ffj For(j, 0, M) #define ffa ffi ffj #define s <<" "<< #define c <<" : "<< #define w cout #define e endl//"\n" #define pb push_back #define mp make_pair #define a first #define b second //#define int ll const int MAXN=1000000; ///500,000,000 int N, comp[MAXN], cat, nonn[MAXN], st[MAXN], nd[MAXN]; ll siz[MAXN], out, ns[MAXN], pre1[MAXN], pre2[MAXN], suf1[MAXN], suf2[MAXN], ans[MAXN]; bool vis[MAXN], cyc[MAXN]; queue<int> next1; vector<pair<int, int> > adj[MAXN]; /// (node, cost) void go(int at) { if (comp[at] != -1) return; comp[at] = cat; for (auto i: adj[at]) go(i.a); } void calc_size(int at) { if (vis[at]) return; vis[at] = true; if (adj[at].size() == 1) return; ll b1 = 0, b2 = 0; for (auto i: adj[at]) if (!cyc[i.a] && !vis[i.a]) { calc_size(i.a); siz[at] = max(siz[at], i.b+siz[i.a]); if (siz[i.a]+i.b >= b1) {b2 = b1; b1 = i.b+siz[i.a];} else if (siz[i.a]+i.b > b2) {b2 = i.b+siz[i.a];} } //w<< at+1 c b1 s b2<<e; ans[comp[at]] = max(ans[comp[at]], b1+b2); } ll solve (int x) { ll ret = 0; int loc = 0; int at = st[x]; //w<< "comp" s x <<e; while (at != st[x] || loc == 0) { //w<< at+1<<e; ns[loc] = siz[at]; vis[at] = true; bool found = false; for (auto i: adj[at]) if (!vis[i.a]) { nd[loc] = i.b; at = i.a; found = true; break; } if (!found) { vis[st[x]] = false; for (auto i: adj[at]) if (!vis[i.a]) { nd[loc] = i.b; at = i.a; } } loc++; } if (loc == 1) {while (true){}} assert(loc != 1); /// edge from x to x //For (i, 0, loc) w<< ns[i] s nd[i]<<e; pre1[0] = ns[0]; ll curr = 0; For (i, 1, loc) { curr += nd[i-1]; pre1[i] = max(pre1[i-1], curr+ns[i]); ret = max(ret, curr+ns[0] + ns[i]); } //For (i, 0, loc) w<< "pre1" s i c pre1[i]<<e; suf1[loc-1] = nd[loc-1] + ns[loc-1]; curr = nd[loc-1]; for (int i=loc-2; i>=1; i--) { curr += nd[i]; suf1[i] = max(suf1[i+1], curr+ns[i]); } //For (i, 0, loc) w<< "suf1" s i c suf1[i]<<e; For (i, 0, loc-1) ret = max(ret, pre1[i] + suf1[i+1]); //w<< "from pass 1, ret =" s ret<<e; pre2[0] = ns[0]; For (i, 1, loc) pre2[i] = max(pre2[i-1]+nd[i-1], ns[i]); //For (i, 0, loc) w<< "pre2" s i c pre2[i]<<e; suf2[loc-1] = 0; for (int i=loc-2; i>=0; i--) suf2[i] = max(suf2[i+1]+nd[i], ns[i+1]+nd[i]); //For (i, 0, loc) w<< "suf2" s i c suf2[i]<<e; For (i, 0, loc) ret = max(ret, pre2[i]+suf2[i]); //w<< "after pass 2, ret =" s ret<<e; return max(ret, ans[x]); } main() { //ifstream cin("test.in"); ios_base::sync_with_stdio(0); cin.tie(0); cin >> N; ffi {cyc[i] = true; comp[i] = -1; int b, d; cin >> b >> d; b--; if (i != b) {adj[i].pb(mp(b, d)); adj[b].pb(mp(i, d));}} ffi if (comp[i] == -1) {go(i); cat++;} ffi if (adj[i].size() == 1) next1.push(i); while (!next1.empty()) { int at = next1.front(); next1.pop(); if (!cyc[at]) continue; if (nonn[at] == adj[at].size()-1) { cyc[at] = false; for (auto i: adj[at]) { nonn[i.a]++; if (cyc[i.a]) next1.push(i.a); } } } //ffi w<< i+1 c cyc[i]<<e; ffi if (cyc[i]) {st[comp[i]] = i; calc_size(i);} //ffi w<< i+1 c siz[i]<<e; ffi { vis[i] = false; if (!cyc[i]) vis[i] = true; } For (i, 0, cat) out += solve(i); w<< out <<e; }

Compilation message (stderr)

islands.cpp:101:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
islands.cpp: In function 'int main()':
islands.cpp:111:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (nonn[at] == adj[at].size()-1) {
             ~~~~~~~~~^~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...