| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 116636 | 2019-06-13T09:19:18 Z | KLPP | Islands (IOI08_islands) | C++14 | 455 ms | 131072 KB |
#include<bits/stdc++.h>
using namespace std;
typedef long long int lld;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
#define INF 1000000000000000
typedef pair<lld,lld> pii;
vector<pii> nei[1000000];
int n;
int comp[1000000];
lld cost[1000000];
int edge[1000000];
vector<vector<int> >cmp;
void DFS(int node){
cmp[cmp.size()-1].push_back(node);
comp[node]=cmp.size()-1;
trav(a,nei[node]){
if(comp[a.first]==-1)DFS(a.first);
}
}
lld comp_ans[1000000];
bool visited[1000000];
int parent[1000000];
int dfs_low[1000000];
int dfs_num[1000000];
int cnt;
int CNT;
stack<int> s;
int BCC[1000000];
vector<vector<int> > cycles;
void DFS2(int node){
dfs_low[node]=cnt;
dfs_num[node]=cnt;
cnt++;
s.push(node);
visited[node]=true;
trav(a,nei[node]){
if(!visited[a.first]){
parent[a.first]=a.second;
DFS2(a.first);
}
if(parent[node]!=a.second && visited[a.first]){
//cout<<node<<" "<<a.first<<endl;
dfs_low[node]=min(dfs_low[node],dfs_low[a.first]);
}
}
if(dfs_low[node]==dfs_num[node]){
//cout<<"A"<<node<<endl;
vector<int> V;
cycles.push_back(V);
while(true){
int u=s.top();
BCC[u]=CNT;
visited[u]=false;
s.pop();
cycles[cycles.size()-1].push_back(u);
if(u==node){
break;
}
}
CNT++;
}
}
vector<pii> tree[1000000];
vector<pii> child[1000000];
lld path[1000000];
lld diam[1000000];
void DFS3(int node){
visited[node]=true;
path[node]=0;
diam[node]=0;
trav(a,tree[node]){
if(!visited[a.first]){
child[node].push_back(a);
DFS3(a.first);
}
}
lld best,second;
best=0;
second=0;
trav(a,child[node]){
path[node]=max(path[a.first]+a.second,path[node]);
diam[node]=max(diam[node],diam[a.first]);
if(path[a.first]+a.second>=best){
second=best;
best=path[a.first]+a.second;
}else{
second=max(second,path[a.first]+a.second);
}
}
diam[node]=max(diam[node],best+second);
}
int main(){
scanf("%d",&n);
rep(i,0,n){
lld x,y;
scanf("%lld %lld",&x,&y);
x--;
nei[i].push_back(pii(x,i));
nei[x].push_back(pii(i,i));
cost[i]=y;
edge[i]=x;
}
rep(i,0,n)comp[i]=-1;
rep(i,0,n){
visited[i]=false;
dfs_low[i]=-1;
dfs_num[i]=-1;
if(comp[i]==-1){
vector<int> V;
comp_ans[cmp.size()]=-1;
cmp.push_back(V);
DFS(i);
}
}
cnt=0;
CNT=0;
rep(i,0,cmp.size()){
//cout<<cmp[i][0]<<endl;
DFS2(cmp[i][0]);
}
/*rep(i,0,n)cout<<BCC[i]<<endl;
rep(i,0,cycles.size()){
trav(a,cycles[i])cout<<a<<" ";
cout<<endl;
}*/
rep(i,0,n){
if(BCC[i]!=BCC[edge[i]]){
//cout<<i<<" "<<edge[i]<<endl;
tree[i].push_back(pii(edge[i],cost[i]));
tree[edge[i]].push_back(pii(i,cost[i]));
}
}
rep(i,0,cycles.size()){
if(cycles[i].size()>1){
trav(a,cycles[i]){
DFS3(a);
comp_ans[comp[a]]=max(comp_ans[comp[a]],diam[a]);
}
vector<int> v1,v2;
int start=cycles[i][0];
do{
v1.push_back(path[start]);
v2.push_back(cost[start]);
start=edge[start];
}while(start!=cycles[i][0]);
lld best=INF;
lld sum=0;
lld S=0;
rep(j,0,v1.size()){
//cout<<sum<<" "<<v1[j]<<" "<<best<<" "<<comp[i]<<endl;
comp_ans[comp[start]]=max(comp_ans[comp[start]],sum+v1[j]-best);
best=min(best,sum-v1[j]);
sum+=v2[j];
S+=v2[j];
}
sum=0;
best=INF;
rep(j,0,v1.size()){
comp_ans[comp[start]]=max(comp_ans[comp[start]],S-sum+v1[j]-best);
best=min(best,-sum-v1[j]);
sum+=v2[j];
}
}
}
lld res=0;
rep(i,0,cmp.size()){
//cout<<comp_ans[i]<<endl;
res+=comp_ans[i];
}
printf("%lld\n",res);
return 0;
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 65 ms | 70824 KB | Output is correct |
| 2 | Correct | 62 ms | 70876 KB | Output is correct |
| 3 | Correct | 64 ms | 70976 KB | Output is correct |
| 4 | Correct | 72 ms | 70904 KB | Output is correct |
| 5 | Correct | 64 ms | 70904 KB | Output is correct |
| 6 | Correct | 208 ms | 70904 KB | Output is correct |
| 7 | Correct | 73 ms | 70904 KB | Output is correct |
| 8 | Correct | 66 ms | 70888 KB | Output is correct |
| 9 | Correct | 64 ms | 70904 KB | Output is correct |
| 10 | Correct | 66 ms | 70904 KB | Output is correct |
| 11 | Correct | 64 ms | 70948 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 67 ms | 71124 KB | Output is correct |
| 2 | Correct | 65 ms | 71160 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 64 ms | 71288 KB | Output is correct |
| 2 | Correct | 66 ms | 71872 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 79 ms | 74204 KB | Output is correct |
| 2 | Correct | 102 ms | 79764 KB | Output is correct |
| 3 | Incorrect | 88 ms | 76080 KB | Output isn't correct |
| 4 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 116 ms | 83504 KB | Output is correct |
| 2 | Correct | 126 ms | 90668 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 273 ms | 120536 KB | Output is correct |
| 2 | Correct | 236 ms | 117304 KB | Output is correct |
| 3 | Runtime error | 264 ms | 131072 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 291 ms | 131072 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 408 ms | 131072 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 455 ms | 131072 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 | Halted | 0 ms | 0 KB | - |