| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 506118 |
2022-01-11T15:59:56 Z |
blue |
Islands (IOI08_islands) |
C++17 |
|
755 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);
}
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;
vi ring;
vll 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 |
37 ms |
84412 KB |
Output is correct |
| 2 |
Correct |
36 ms |
84392 KB |
Output is correct |
| 3 |
Correct |
35 ms |
84424 KB |
Output is correct |
| 4 |
Correct |
34 ms |
84420 KB |
Output is correct |
| 5 |
Correct |
39 ms |
84432 KB |
Output is correct |
| 6 |
Correct |
40 ms |
84476 KB |
Output is correct |
| 7 |
Correct |
34 ms |
84428 KB |
Output is correct |
| 8 |
Correct |
35 ms |
84392 KB |
Output is correct |
| 9 |
Correct |
35 ms |
84384 KB |
Output is correct |
| 10 |
Correct |
37 ms |
84440 KB |
Output is correct |
| 11 |
Correct |
35 ms |
84436 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
84548 KB |
Output is correct |
| 2 |
Correct |
36 ms |
84492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
39 ms |
84496 KB |
Output is correct |
| 2 |
Correct |
40 ms |
84852 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
49 ms |
85376 KB |
Output is correct |
| 2 |
Correct |
68 ms |
87868 KB |
Output is correct |
| 3 |
Correct |
60 ms |
85528 KB |
Output is correct |
| 4 |
Correct |
43 ms |
84920 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
85 ms |
89144 KB |
Output is correct |
| 2 |
Correct |
124 ms |
90160 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
189 ms |
96036 KB |
Output is correct |
| 2 |
Correct |
256 ms |
102288 KB |
Output is correct |
| 3 |
Correct |
308 ms |
113992 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
404 ms |
101744 KB |
Output is correct |
| 2 |
Runtime error |
413 ms |
131076 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
755 ms |
131076 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
732 ms |
131076 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
