Submission #390259

#TimeUsernameProblemLanguageResultExecution timeMemory
390259parsabahramiIslands (IOI08_islands)C++17
80 / 100
1796 ms131076 KiB
/* There's someone in my head but it's not me */ #include <bits/stdc++.h> using namespace std; typedef long long int ll; typedef pair<int, int> pii; #define SZ(x) (int) x.size() #define F first #define S second const int N = 1e6 + 1; int n, rt[N], P[N], out[N], w[N], R; ll A[N], ret[N], H[N], S; vector<int> adj[N], vec, bads; bitset<N> C; int Find(int v) { return !rt[v] ? v : rt[v] = Find(rt[v]); } int Union(int v, int u) { u = Find(u), v = Find(v); if (u == v) return 1; rt[u] = v; return 0; } void preDFS(int v, int tr, int p = -1) { vec.push_back(v); adj[v].push_back(v); for (int &id : adj[v]) { int u = out[id] ^ id ^ v; if ((!C[u] || u == tr) && u != p) H[u] = H[v] + w[id], preDFS(u, tr, v); } adj[v].pop_back(); } void cycDFS(int v, int tr, int p = -1) { adj[v].push_back(v); for (int &id : adj[v]) { if (id != tr) { int u = out[id] ^ id ^ v; if (u != p) P[u] = id, cycDFS(u, tr, v); } } adj[v].pop_back(); } ll CYC(int &v, int p = -1) { ll ans = -1e18; adj[v].push_back(v); for (int &id : adj[v]) { int u = out[id] ^ id ^ v; if (C[u] && u != p && u != R) { H[u] = H[v] + w[id], ans = CYC(u, v); break; } } adj[v].pop_back(); ret[Find(v)] = max(ret[Find(v)], ans + A[v] - H[v]); return max(ans, A[v] + H[v]); } ll CYC2(int &v, int p = -1) { ll ans = -1e18; adj[v].push_back(v); for (int &id : adj[v]) { int u = out[id] ^ id ^ v; if (C[u] && u != p && u != R) { ans = CYC2(u, v); break; } } adj[v].pop_back(); ret[Find(v)] = max(ret[Find(v)], ans + A[v] + H[v]); return max(ans, S - H[v] + A[v]); } int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d%d", &out[i], &w[i]); adj[out[i]].push_back(i); if (Union(i, out[i])) bads.push_back(i); } for (int &id : bads) { cycDFS(out[id], id); int v = id; C[out[id]] = 1; while (P[v]) C[v] = 1, v = out[P[v]] ^ P[v] ^ v; } for (int i = 1; i <= n; i++) { if (!C[i]) continue; vec = {}, preDFS(i, i); vec.shrink_to_fit(); int b = -1; for (int &v : vec) if (!~b || H[b] < H[v]) b = v; A[i] = H[b]; vec = {}; H[b] = 0, preDFS(b, i); b = -1; for (int v : vec) if (!~b || H[b] < H[v]) b = v; ret[Find(i)] = max(ret[Find(i)], H[b]); } ll res = 0; vec = {}, vec.shrink_to_fit(); for (; SZ(bads); bads.pop_back()) { R = bads.back(); H[R] = 0; S = w[R]; int v = R; while (P[v]) S += w[P[v]], v = P[v] ^ v ^ out[P[v]]; CYC(R), CYC2(R); res += ret[Find(R)]; } printf("%lld\n", res); return 0; }

Compilation message (stderr)

islands.cpp: In function 'int main()':
islands.cpp:78:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   78 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
islands.cpp:80:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   80 |         scanf("%d%d", &out[i], &w[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#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...