Submission #407242

#TimeUsernameProblemLanguageResultExecution timeMemory
407242Aldas25Islands (IOI08_islands)C++14
60 / 100
2078 ms131076 KiB
#pragma GCC optimize("O2") #include <bits/stdc++.h> using namespace std; #define FAST_IO ios_base::sync_with_stdio(0); cin.tie(0) #define FOR(i, a, b) for(int i = (a); i <= (b); i++) #define REP(n) FOR(O, 1, (n)) #define pb push_back #define f first #define s second typedef long double ld; typedef long long ll; typedef pair<int, int> pii; typedef pair<int, pii> piii; typedef vector<int> vi; typedef vector<pii> vii; typedef vector<ll> vl; typedef vector<piii> viii; const int MAXN = 1000100, MAXK = 30; //const ll MOD = 998244353; const ll INF = 1e17; const ld PI = asin(1) * 2; int n; vii adj[MAXN]; ll dp[MAXN][2]; bool inCycle[MAXN]; bool vis[MAXN]; stack<int> st; vi cycle; ll cycleWalkLen = 0; ll enterD[MAXN]; void dfs1 (int v, int p = -1) { vis[v] = true; st.push(v); for (auto pp : adj[v]) { int u = pp.f; ll l = pp.s; if (u == p) { p = -1; continue; } if (!vis[u]) { enterD[u] = enterD[v] + l; dfs1(u, v); } else { if ((int)cycle.size() == 0) { cycleWalkLen = enterD[v] - enterD[u] + l; while (st.top() != u) { cycle.pb(st.top()); //cout << " pushing " << st.top(); st.pop(); } cycle.pb(u); // cout << " pushing u = "<<u<< endl; } } } if(!st.empty()) st.pop(); } ll mxPath = 0; void dfs2(int v,int p = -1) { for (auto pp : adj[v]) { int u = pp.f; ll l = pp.s; if (inCycle[u] || u == p) continue; dfs2(u, v); ll cr = dp[u][0] + l; if (cr > dp[v][0]) { dp[v][1] = dp[v][0]; dp[v][0] = cr; } else if (cr > dp[v][1]) { dp[v][1] = cr; } } mxPath = max(mxPath, dp[v][0] + dp[v][1]); } int to[MAXN]; ll toLen[MAXN]; ll pref[MAXN]; ll getW (int a, int b) { //cout << " getW a = " << a <<" b = " << b << endl; //cout << " toA = " << to[a] << " toB = " << to[b] << endl; if (to[a] != b) swap(a,b); //cout << " b=" << b << "-> " << " a=" << a << " to[b] = " << to[b] << " tolen[b] = " << toLen[b] //<< endl; return toLen[a]; } int main() { FAST_IO; cin >> n; FOR(i, 1, n) { int u; ll l; cin >> u >> l; to[i] = u; toLen[i] = l; adj[i].pb({u, l}); adj[u].pb({i, l}); } ll ans = 0; FOR(i, 1, n) { if (vis[i]) continue; // cout << " i = " << i << endl; cycle.clear(); cycleWalkLen = 0; dfs1(i); int len = (int)cycle.size(); for (int x : cycle) { inCycle[x] = true; //cout << " incycle x=" << x << endl; } FOR(a, 1, len-1) { int v = cycle[a]; int pr = cycle[a-1]; pref[a] = pref[a-1] + getW (v, pr); // cout << " pref[" << a << "] = " << pref[a] << endl; // cout << " v = " << v << " pr = " << pr << " getw = " << getW(v,pr) << endl; } ll curMax = 0; //cout << " cycleWalkLen = " << cycleWalkLen << endl; for (int x : cycle) { mxPath = 0; dfs2(x); curMax = max(curMax, mxPath); //cout << " x = " << x << " mxPath = " << mxPath << endl; } FOR(a, 0, len-1) FOR(b, a+1, len-1) { ll cr = dp[cycle[a]][0] + dp[cycle[b]][0]; cr += max(pref[b] - pref[a], cycleWalkLen-pref[b]+pref[a]); curMax = max(curMax, cr); //cout << " a = " << a << " b = " << b << " u=" << cycle[a] << " v=" << cycle[b] <<" cr=" << cr << endl; } ans += curMax; } cout << ans << "\n"; return 0; }
#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...