# |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
53750 |
2018-07-01T06:37:00 Z |
노영훈(#1436) |
Islands (IOI08_islands) |
C++11 |
|
2000 ms |
186872 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, ll> pil;
const int MX=1000010;
const ll inf=2e17;
int n, A[MX], C[MX];
vector<pil> G[MX];
bool done[MX];
ll D[MX];
bool vis[MX];
// list all vertices
void dfs1(int v, vector<int> &V){
done[v]=true;
V.push_back(v);
for(pil &e:G[v]){
int x=e.first;
if(done[x]) continue;
dfs1(x,V);
}
}
// find cycle
int found=-1;
int dep[MX], now;
void dfs2(int v, int p, vector<int> &V){
dep[v]=++now;
for(pil &e:G[v]){
int x; ll c; tie(x,c)=e;
if(p==x) continue;
if(dep[x]>=0)
found=x;
else
dfs2(x,v,V);
if(found>=0){
if(dep[v]>=dep[found]) V.push_back(v);
return;
}
}
--now;
}
// farthest point
ll dist[MX];
int dfs3(int v){
int res=v;
for(pil &e:G[v]){
int x; ll c; tie(x,c)=e;
if(dist[x]>=0) continue;
dist[x]=dist[v]+c;
int y=dfs3(x);
if(dist[y]>dist[res]) res=y;
}
return res;
}
ll solve_tree(vector<int> &V){
int s=V[0];
for(int v:V) dist[v]=-1;
dist[s]=0;
int u=dfs3(s);
for(int v:V) dist[v]=-1;
dist[u]=0;
int v=dfs3(u);
return dist[v];
}
bool incyc[MX];
ll arm[MX];
// longest path from v in cyc
void dfs4(int v, int p=-1){
arm[v]=0;
for(pil &e:G[v]){
int x; ll c; tie(x,c)=e;
if(incyc[x] || x==p) continue;
if(arm[x]<0) dfs4(x,v);
arm[v]=max(arm[v], arm[x]+c);
}
}
ll Val[MX], Len[MX], Sum[MX];
vector<int> V, cyc;
ll solve(int s){
// cout<<"\nSOLVE ON "<<s<<'\n';
V.clear(), cyc.clear();
dfs1(s, V);
found=-1, now=0;
for(int v:V) dep[v]=-1;
dfs2(s, -1, cyc);
if(cyc.empty())
return solve_tree(V);
for(int v:V) arm[v]=-1;
for(int v:cyc) incyc[v]=true, arm[v]=0;
for(int v:cyc) dfs4(v);
int sz=cyc.size();
Sum[1]=0;
for(int i=0; i<sz; i++){
int v=cyc[i];
Val[i]=arm[v];
int nxt=cyc[(i+1)%sz];
for(pil &e:G[v]) if(e.first==nxt) Len[i]=e.second;
Sum[i+1]=Sum[i]+Len[i];
}
ll res=0;
for(int i=0; i<2*sz; i++){
}
for(int i=0; i<sz; i++)
for(int j=i+1; j<sz; j++){
ll dist=max(Sum[j]-Sum[i], Sum[sz]+Sum[i]-Sum[j]);
ll now=dist+Val[i]+Val[j];
// printf("%d - %d : %lld (%lld)\n", cyc[i], cyc[j], now, dist);
res=max(res, now);
}
return res;
}
int main(){
ios::sync_with_stdio(0); cin.tie(0);
cin>>n;
for(int u=1; u<=n; u++){
int v, c; cin>>v>>c;
A[u]=v, C[u]=c;
if(A[v]==u){
C[u]=max(C[u], C[v]);
C[v]=-1;
}
}
for(int i=1; i<=n; i++){
if(C[i]<0) continue;
G[i].push_back({A[i], C[i]});
G[A[i]].push_back({i, C[i]});
}
ll ans=0;
for(int i=1; i<=n; i++){
if(done[i]) continue;
ans+=solve(i);
}
cout<<ans;
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
23 ms |
23892 KB |
Output is correct |
2 |
Incorrect |
22 ms |
23912 KB |
Output isn't correct |
3 |
Correct |
27 ms |
24092 KB |
Output is correct |
4 |
Correct |
24 ms |
24092 KB |
Output is correct |
5 |
Correct |
24 ms |
24092 KB |
Output is correct |
6 |
Correct |
22 ms |
24096 KB |
Output is correct |
7 |
Correct |
23 ms |
24096 KB |
Output is correct |
8 |
Correct |
24 ms |
24124 KB |
Output is correct |
9 |
Correct |
23 ms |
24124 KB |
Output is correct |
10 |
Correct |
24 ms |
24124 KB |
Output is correct |
11 |
Correct |
23 ms |
24124 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
24 ms |
24236 KB |
Output is correct |
2 |
Correct |
23 ms |
24236 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
23 ms |
24300 KB |
Output is correct |
2 |
Correct |
28 ms |
24564 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
50 ms |
25460 KB |
Output is correct |
2 |
Correct |
260 ms |
28392 KB |
Output is correct |
3 |
Correct |
38 ms |
28392 KB |
Output is correct |
4 |
Correct |
39 ms |
28392 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
496 ms |
29892 KB |
Output is correct |
2 |
Correct |
559 ms |
33148 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
511 ms |
41244 KB |
Output is correct |
2 |
Execution timed out |
2025 ms |
45284 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1337 ms |
54552 KB |
Output is correct |
2 |
Execution timed out |
2049 ms |
82032 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
436 ms |
99636 KB |
Output is correct |
2 |
Execution timed out |
2064 ms |
152788 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
639 ms |
157020 KB |
Output is correct |
2 |
Correct |
712 ms |
157020 KB |
Output is correct |
3 |
Execution timed out |
2067 ms |
186872 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |