| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 116639 |
2019-06-13T09:31:40 Z |
KLPP |
Islands (IOI08_islands) |
C++14 |
|
334 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<int >cmp[1000000];
int COMPS;
void DFS(int node){
cmp[COMPS].push_back(node);
comp[node]=COMPS;
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;
COMPS=0;
rep(i,0,n){
visited[i]=false;
dfs_low[i]=-1;
dfs_num[i]=-1;
if(comp[i]==-1){
comp_ans[COMPS]=-1;
DFS(i);
COMPS++;
}
}
cnt=0;
CNT=0;
rep(i,0,COMPS){
//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]));
}
}
vector<int> v1,v2;
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]);
}
v1.clear();
v2.clear();
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,COMPS){
//cout<<comp_ans[i]<<endl;
res+=comp_ans[i];
}
printf("%lld\n",res);
return 0;
}
Compilation message
islands.cpp: In function 'int main()':
islands.cpp:5:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define rep(i,a,b) for(int i=a;i<b;i++)
islands.cpp:140:7:
rep(i,0,cycles.size()){
~~~~~~~~~~~~~~~~~
islands.cpp:140:3: note: in expansion of macro 'rep'
rep(i,0,cycles.size()){
^~~
islands.cpp:5:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define rep(i,a,b) for(int i=a;i<b;i++)
islands.cpp:157:11:
rep(j,0,v1.size()){
~~~~~~~~~~~~~
islands.cpp:157:7: note: in expansion of macro 'rep'
rep(j,0,v1.size()){
^~~
islands.cpp:5:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define rep(i,a,b) for(int i=a;i<b;i++)
islands.cpp:166:11:
rep(j,0,v1.size()){
~~~~~~~~~~~~~
islands.cpp:166:7: note: in expansion of macro 'rep'
rep(j,0,v1.size()){
^~~
islands.cpp:99:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
islands.cpp:102:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld %lld",&x,&y);
~~~~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
97 ms |
94328 KB |
Output is correct |
| 2 |
Correct |
92 ms |
94416 KB |
Output is correct |
| 3 |
Correct |
89 ms |
94456 KB |
Output is correct |
| 4 |
Correct |
86 ms |
94456 KB |
Output is correct |
| 5 |
Correct |
86 ms |
94296 KB |
Output is correct |
| 6 |
Correct |
88 ms |
94388 KB |
Output is correct |
| 7 |
Correct |
87 ms |
94328 KB |
Output is correct |
| 8 |
Correct |
87 ms |
94372 KB |
Output is correct |
| 9 |
Correct |
88 ms |
94428 KB |
Output is correct |
| 10 |
Correct |
83 ms |
94456 KB |
Output is correct |
| 11 |
Correct |
88 ms |
94328 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
88 ms |
94612 KB |
Output is correct |
| 2 |
Correct |
87 ms |
94516 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
88 ms |
94664 KB |
Output is correct |
| 2 |
Correct |
87 ms |
95300 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
102 ms |
97332 KB |
Output is correct |
| 2 |
Correct |
134 ms |
102860 KB |
Output is correct |
| 3 |
Incorrect |
118 ms |
99248 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
141 ms |
106288 KB |
Output is correct |
| 2 |
Correct |
152 ms |
113044 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
219 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 |
251 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 |
278 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 |
334 ms |
131072 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
