| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 506105 |
2022-01-11T15:44:03 Z |
blue |
Islands (IOI08_islands) |
C++17 |
|
757 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 = 1'000'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);
}
}
vi cyclic(1+maxN, 1);
vi indegree(1+maxN, 0);
int tree_ct;
vi visit1(1+maxN, 0), visit2(1+maxN, 0);
vll dist1(1+maxN, 0), dist2(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]);
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;
}
}
// 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, dist2[u]);
for(pii v: edge[u])
{
if((cyclic[v.first] && cyclic[u]) || visit2[v.first]) continue;
visit2[v.first] = 1;
dist2[v.first] = dist2[u] + v.second;
tbv.push(v.first);
}
}
// cerr << "tree diam from " << src << " = " << res << '\n';
return res;
}
int z;
vll ring, outer, x;
ll tot;
ll fwd_dist(int u, int v)
{
if(x[u] <= x[v]) return x[v] - x[u];
else return tot - x[u] + x[v];
}
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);
for(int i = 0; i < z; i++)
{
ring.push_back(ring[i]);
outer.push_back(outer[i]);
}
// 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];
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]);
}
// cerr << "#\n";
for(int i = z-1; i < 2*z; i++)
{
// cerr << i << '\n';
res = max(res, x[i] + outer[i] + *val.rbegin());
// cerr << "p\n";
val.insert(-x[i] + outer[i]);
// cerr << "q\n";
val.erase(val.find(-x[i-z+1] + outer[i-z+1]));
// 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 |
44 ms |
98144 KB |
Output is correct |
| 2 |
Correct |
40 ms |
98168 KB |
Output is correct |
| 3 |
Correct |
40 ms |
98192 KB |
Output is correct |
| 4 |
Correct |
39 ms |
98116 KB |
Output is correct |
| 5 |
Correct |
39 ms |
98104 KB |
Output is correct |
| 6 |
Correct |
42 ms |
98100 KB |
Output is correct |
| 7 |
Correct |
40 ms |
98064 KB |
Output is correct |
| 8 |
Correct |
43 ms |
98168 KB |
Output is correct |
| 9 |
Correct |
41 ms |
98160 KB |
Output is correct |
| 10 |
Correct |
44 ms |
98108 KB |
Output is correct |
| 11 |
Correct |
40 ms |
98056 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
43 ms |
98268 KB |
Output is correct |
| 2 |
Correct |
48 ms |
98200 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
42 ms |
98252 KB |
Output is correct |
| 2 |
Correct |
44 ms |
98628 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
56 ms |
99216 KB |
Output is correct |
| 2 |
Correct |
74 ms |
102328 KB |
Output is correct |
| 3 |
Correct |
61 ms |
99324 KB |
Output is correct |
| 4 |
Correct |
50 ms |
98696 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
93 ms |
103848 KB |
Output is correct |
| 2 |
Correct |
129 ms |
106060 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
203 ms |
112460 KB |
Output is correct |
| 2 |
Correct |
285 ms |
119644 KB |
Output is correct |
| 3 |
Correct |
330 ms |
131072 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
413 ms |
121808 KB |
Output is correct |
| 2 |
Runtime error |
366 ms |
131076 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
636 ms |
131076 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
757 ms |
131076 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
