oj.uz

Submission #116638

# Submission time Handle Problem Language Result Execution time Memory
116638 2019-06-13T09:25:22 Z KLPP Islands (IOI08_islands) C++14
50 / 100
 446 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]));
    }
  }
  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,cmp.size()){
    //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:122:7:
   rep(i,0,cmp.size()){
       ~~~~~~~~~~~~~~             
islands.cpp:122:3: note: in expansion of macro 'rep'
   rep(i,0,cmp.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:139:7:
   rep(i,0,cycles.size()){
       ~~~~~~~~~~~~~~~~~          
islands.cpp:139: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:156:11:
       rep(j,0,v1.size()){
           ~~~~~~~~~~~~~          
islands.cpp:156: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:165:11:
       rep(j,0,v1.size()){
           ~~~~~~~~~~~~~          
islands.cpp:165: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:173:7:
   rep(i,0,cmp.size()){
       ~~~~~~~~~~~~~~             
islands.cpp:173:3: note: in expansion of macro 'rep'
   rep(i,0,cmp.size()){
   ^~~
islands.cpp:98:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&n);
   ~~~~~^~~~~~~~~
islands.cpp:101:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld %lld",&x,&y);
     ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 70908 KB Output is correct
2 Correct 73 ms 70904 KB Output is correct
3 Correct 67 ms 70904 KB Output is correct
4 Correct 67 ms 70904 KB Output is correct
5 Correct 73 ms 70884 KB Output is correct
6 Correct 67 ms 70776 KB Output is correct
7 Correct 65 ms 70904 KB Output is correct
8 Correct 61 ms 70904 KB Output is correct
9 Correct 62 ms 70904 KB Output is correct
10 Correct 64 ms 70904 KB Output is correct
11 Correct 66 ms 70876 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 71032 KB Output is correct
2 Correct 69 ms 71288 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 71248 KB Output is correct
2 Correct 74 ms 71788 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 73940 KB Output is correct
2 Correct 128 ms 79420 KB Output is correct
3 Incorrect 105 ms 75828 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 82900 KB Output is correct
2 Correct 138 ms 89504 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 285 ms 117936 KB Output is correct
2 Correct 236 ms 114756 KB Output is correct
3 Runtime error 240 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 283 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 393 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 446 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -