| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 506116 |
2022-01-11T15:58:41 Z |
blue |
Islands (IOI08_islands) |
C++17 |
|
652 ms |
131076 KB |
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using vvi = vector<int>;
using vvll = vector<vll>;
using pii = pair<int, int>;
#define sz(x) int(x.size())
const int maxN = 800'000;
int N;
vi A(1+maxN);
vi L(1+maxN);
vector<pii>* edge = new vector<pii>[1+maxN];
int ct = 0;
vi cc(1+maxN, 0);
vi cc_list[1+maxN];
void dfs1(int u)
{
cc[u] = ct;
cc_list[cc[u]].push_back(u);
for(pii v: edge[u])
{
if(cc[v.first]) continue;
dfs1(v.first);
}
if(!cc[A[u]]) dfs1(A[u]);
}
vector<short> cyclic(1+maxN, 1);
vi indegree(1+maxN, 0);
int tree_ct;
vector<short> visit1(1+maxN, 0), visit2(1+maxN, 0);
vll dist1(1+maxN, 0);
vll depth(1+maxN, 0);
ll find_tree_diameter(int src)
{
// cerr << "\n calling find tree diameter from " << src << '\n';
queue<int> tbv;
tbv.push(src);
visit1[src] = 1;
int opp = src;
while(!tbv.empty())
{
int u = tbv.front();
tbv.pop();
depth[src] = max(depth[src], dist1[u]);
edge[u].push_back({A[u], L[u]});
for(pii v: edge[u])
{
if((cyclic[v.first] && cyclic[u]) || visit1[v.first]) continue;
visit1[v.first] = 1;
dist1[v.first] = dist1[u] + v.second;
tbv.push(v.first);
if(dist1[v.first] > dist1[opp]) opp = v.first;
}
edge[u].pop_back();
dist1[u] = 0;
}
// cerr << "opp = " << opp << '\n';
ll res = 0;
tbv.push(opp);
visit2[opp] = 1;
while(!tbv.empty())
{
int u = tbv.front();
tbv.pop();
// cerr << "bfs2: " << u << '\n';
res = max(res, dist1[u]);
edge[u].push_back({A[u], L[u]});
for(pii v: edge[u])
{
if((cyclic[v.first] && cyclic[u]) || visit2[v.first]) continue;
visit2[v.first] = 1;
dist1[v.first] = dist1[u] + v.second;
tbv.push(v.first);
}
edge[u].pop_back();
}
// cerr << "tree diam from " << src << " = " << res << '\n';
return res;
}
int z;
vll ring, outer, x;
ll tot;
ll solve(vi lst)
{
// cerr << "calling solve: ";
// for(int u: lst) cerr << u << ' ';
// cerr << '\n';
queue<int> tbv;
for(int u: lst) if(!indegree[u]) tbv.push(u);
while(!tbv.empty())
{
int u = tbv.front();
tbv.pop();
cyclic[u] = 0;
indegree[A[u]]--;
if(!indegree[A[u]]) tbv.push(A[u]);
}
ll tree_diam = 0;
ring.clear();
outer.clear();
// cerr << "A\n";
int r = 0;
for(int u: lst)
{
if(!cyclic[u]) continue;
if(!r) r = u;
tree_ct++;
tree_diam = max(tree_diam, find_tree_diameter(u));
}
// cerr << "B\n";
int y = r;
while(1)
{
ring.push_back(L[y]);
outer.push_back(depth[y]);
y = A[y];
if(y == r) break;
}
z = sz(ring);
// cerr << "component: \n";
//
// for(int i = 0; i < z; i++) cerr << ring[i] << ' ' << outer[i] << "\n";
//
// cerr << "\n\n";
//
// cerr << "C\n";
x = vll(2*z, 0);
for(int i = 1; i < 2*z; i++) x[i] = x[i-1] + ring[(i-1)%z];
tot = x[z];
multiset<ll> val;
ll res = 0;
// cerr << "D\n";
// cerr << z << '\n';
for(int i = 0; i < z-1; i++)
{
// cerr << i << " : initially inserting " << -x[i] + outer[i] << '\n';
val.insert(-x[i] + outer[i%z]);
}
// cerr << "#\n";
for(int i = z-1; i < 2*z; i++)
{
// cerr << i << '\n';
res = max(res, x[i] + outer[i%z] + *val.rbegin());
// cerr << "p\n";
val.insert(-x[i] + outer[i%z]);
// cerr << "q\n";
val.erase(val.find(-x[i-z+1] + outer[(i-z+1)%z]));
// cerr << "r\n";
}
// int x
// cerr << "tree diameter = " << tree_diam << '\n';
// cerr << "E\n";
// cerr << "return value 1: " << tree_diam << ' ' << res << '\n';
return max(tree_diam, res);
}
int main()
{
cin >> N;
for(int i = 1; i <= N; i++)
{
cin >> A[i] >> L[i];
// edge[i].push_back({A[i], L[i]});
edge[A[i]].push_back({i, L[i]});
indegree[A[i]]++;
}
for(int i = 1; i <= N; i++)
{
if(cc[i]) continue;
ct++;
dfs1(i);
}
ll ans = 0;
for(int c = 1; c <= ct; c++) ans += solve(cc_list[c]);
cout << ans << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
67532 KB |
Output is correct |
| 2 |
Correct |
29 ms |
67588 KB |
Output is correct |
| 3 |
Correct |
28 ms |
67604 KB |
Output is correct |
| 4 |
Correct |
29 ms |
67532 KB |
Output is correct |
| 5 |
Correct |
27 ms |
67548 KB |
Output is correct |
| 6 |
Correct |
29 ms |
67576 KB |
Output is correct |
| 7 |
Correct |
28 ms |
67716 KB |
Output is correct |
| 8 |
Correct |
28 ms |
67532 KB |
Output is correct |
| 9 |
Correct |
27 ms |
67580 KB |
Output is correct |
| 10 |
Correct |
28 ms |
67576 KB |
Output is correct |
| 11 |
Correct |
28 ms |
67648 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
67660 KB |
Output is correct |
| 2 |
Correct |
29 ms |
67608 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
67652 KB |
Output is correct |
| 2 |
Correct |
34 ms |
68004 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
40 ms |
68624 KB |
Output is correct |
| 2 |
Correct |
68 ms |
71164 KB |
Output is correct |
| 3 |
Correct |
44 ms |
68592 KB |
Output is correct |
| 4 |
Correct |
40 ms |
68116 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
76 ms |
72360 KB |
Output is correct |
| 2 |
Correct |
117 ms |
73644 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
178 ms |
79188 KB |
Output is correct |
| 2 |
Correct |
245 ms |
85756 KB |
Output is correct |
| 3 |
Correct |
304 ms |
97768 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
384 ms |
84852 KB |
Output is correct |
| 2 |
Correct |
450 ms |
121600 KB |
Output is correct |
| 3 |
Correct |
649 ms |
128228 KB |
Output is correct |
| 4 |
Runtime error |
601 ms |
131076 KB |
Execution killed with signal 9 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
516 ms |
131072 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
652 ms |
131072 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
