Submission #116639

#	Time	Username	Problem	Language	Result	Execution time	Memory
116639		KLPP	Islands (IOI08_islands)	C++14	50 / 100	334 ms	131072 KiB

islands

#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 (stderr)

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);
     ~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 33 / 33
• Subtask 2: 3 / 3
• Subtask 3: 4 / 4
• Subtask 4: 0 / 10
• Subtask 5: 10 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10