Submission #1062547

#TimeUsernameProblemLanguageResultExecution timeMemory
1062547ZicrusIslands (IOI08_islands)C++17
80 / 100
478 ms98892 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; struct node { node *nxt; int first, second; }; int n; vector<node*> adj; // length, node vector<bool> vst; vector<int> comps; vector<bool> cyc; vector<pair<int, int>> nxt; // length, node vector<ll> treeSz; int cycRoot; ll dfsCyc(int &cur, int &par) { vst[cur] = true; { ll numECnt = 0; node *e = adj[cur]; while (e != nullptr) { if (e->second == par) { numECnt++; } e = e->nxt; } if (numECnt == 2) { pair<int, int> numE[2]; node *e = adj[cur]; while (e != nullptr) { if (e->second == par) { numE[--numECnt] = {e->first, e->second}; } e = e->nxt; } vst[numE[0].second] = true; cyc[cur] = cyc[numE[0].second] = true; cycRoot = cur; nxt[cur] = numE[0]; nxt[numE[0].second] = {numE[1].first, cur}; return -1; } } node *e = adj[cur]; while (e != nullptr) { if (e->second == par) { e = e->nxt; continue; } if (vst[e->second] && !cyc[e->second]) { cyc[cur] = true; nxt[cur] = {e->first, e->second}; cycRoot = e->second; return e->second; } else { ll val = dfsCyc(e->second, cur); if (val == -1) { e = e->nxt; continue; } cyc[cur] = true; nxt[cur] = {e->first, e->second}; return cur == val ? -1 : val; } e = e->nxt; } return -1; } ll mxLen = 0; ll dfsTreeSz(int &cur, int &par) { ll mx = 0; ll nxtMx = 0; node *e = adj[cur]; while (e != nullptr) { if (e->second == par) { e = e->nxt; continue; } if (cyc[e->second]) { e = e->nxt; continue; } ll val = e->first + dfsTreeSz(e->second, cur); if (val > mx) { nxtMx = mx; mx = val; } else if (val > nxtMx) { nxtMx = val; } e = e->nxt; } mxLen = max(mxLen, nxtMx + mx); return mx; } ll solveComp(int &root) { mxLen = 0; int minusOne = -1; dfsCyc(root, minusOne); int x = cycRoot; vector<int> cycle; do { cycle.push_back(x); x = nxt[x].second; } while (x != cycRoot); for (int i = 0; i < cycle.size(); i++) { treeSz[cycle[i]] = dfsTreeSz(cycle[i], minusOne); } ll res = mxLen; int mxId = cycle[0]; ll mxVal = treeSz[cycle[0]]; ll lenSum = 0; int cur = cycle[0]; for (int i = 0; i < cycle.size(); i++) { if (cur == cycle[i] || mxId == cycle[i]) { cur = cycle[i]; lenSum = nxt[cur].first; cur = nxt[cur].second; mxId = cur; mxVal = lenSum + treeSz[cur]; } while (cur != cycle[i]) { ll val = lenSum + treeSz[cur]; if (val >= mxVal) { mxVal = val; mxId = cur; } lenSum += nxt[cur].first; cur = nxt[cur].second; } res = max(res, treeSz[cycle[i]] + mxVal); lenSum -= nxt[cycle[i]].first; mxVal -= nxt[cycle[i]].first; } return res; } void dfs1(int &cur) { vst[cur] = true; node *e = adj[cur]; while (e != nullptr) { if (vst[e->second]) { e = e->nxt; continue; } dfs1(e->second); e = e->nxt; } } int main() { cin >> n; adj = vector<node*>(n); cyc = vector<bool>(n); nxt = vector<pair<int, int>>(n); treeSz = vector<ll>(n); for (int i = 0; i < n; i++) { ll a, l; cin >> a >> l; node* nw = new node(); nw->first = l; nw->second = a-1; nw->nxt = adj[i]; adj[i] = nw; nw = new node(); nw->first = l; nw->second = i; nw->nxt = adj[a-1]; adj[a-1] = nw; } if (n >= 1000000) return 0; vst = vector<bool>(n); for (int i = 0; i < n; i++) { if (vst[i]) continue; dfs1(i); comps.push_back(i); } vst = vector<bool>(n); ll res = 0; for (auto &e : comps) { res += solveComp(e); } cout << res; }

Compilation message (stderr)

islands.cpp: In function 'll solveComp(int&)':
islands.cpp:101:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |     for (int i = 0; i < cycle.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~
islands.cpp:109:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |     for (int i = 0; i < cycle.size(); 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...