Submission #233051

# Submission time Handle Problem Language Result Execution time Memory
233051 2020-05-19T03:50:46 Z FieryPhoenix Islands (IOI08_islands) C++11
0 / 100
1096 ms 131072 KB
#pragma comment(linker, "/STACK: 2000000")
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

#include <bits/stdc++.h>
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef long double ld;
#define INF 2001001001
#define MOD 1000000007
#define f first
#define s second

int N;
ll ans;
int C;
int cycle[1000001],adjDis[1000001];
ll deepest[1000001];
int bad,bad2;
ll maxCur;
map<pair<int,int>,int>mp;
ll pref[1000001],suff[1000001];
pair<pair<int,int>,int> edges[2000005];
int L[1000001],R[1000001];
bool vis[1000001];

int cur;
void findCycle(int node, int par){
  //cout<<"findCycle: "<<node<<endl;
  vis[node]=1; 
  for (int i=L[node];i<=R[node];i++){
    if (C==0 && vis[edges[i].f.s]==0 && edges[i].f.s!=par){ //found cycle
      C=0;
      //cout<<"found cycle"<<endl;
      cur=node;
      while (cur!=edges[i].f.s){
	cycle[C]=cur;
	adjDis[C]=deepest[cur]; //fromDis
	C++;
	cur=pref[cur]; //from
      }
      cycle[C]=edges[i].f.s;
      adjDis[C]=edges[i].s;
      C++;
    }
    else if (vis[edges[i].f.s]==0){ 
      pref[edges[i].f.s]=node; //from
      deepest[edges[i].f.s]=edges[i].s; //fromDis
      findCycle(edges[i].f.s,node);
    }
  }
}

ll maxDis,maxNode;

queue<pair<pair<int,int>,ll>>q;

void findFarthest(int node0, int par0, ll dis0){
  maxDis=-1; maxNode=-1;
  q.push({{node0,par0},dis0});
  while (!q.empty()){
    q.pop();
    int node=q.front().f.f;
    int par=q.front().f.s;
    ll dis=q.front().s;
    q.pop();
    if (dis>maxDis){
      maxDis=dis;
      maxNode=node;
    }
    for (int i=L[node];i<=R[node];i++){
      if (edges[i].f.s!=par && edges[i].f.s!=bad && edges[i].f.s!=bad2)
        q.push({{edges[i].f.s,node},dis+edges[i].s});
    }
  }
}
    

ll findDiameter(int node){
  findFarthest(node,node,0);
  int newNode=maxNode;
  findFarthest(newNode,newNode,0);
  return maxDis;
}

int main()
{
  scanf("%d",&N);
  for (int i=1;i<=N;i++){
    L[i]=INF; R[i]=-INF;
    int Y,L;
    scanf("%d%d",&Y,&L);
    int x=i,y=Y;
    if (x>y) swap(x,y);
    mp[{x,y}]=max(mp[{x,y}],L);
  }
  int E=0;
  for (auto it:mp){
    //cout<<"edge: "<<it.first.first<<' '<<it.first.second<<endl;
    edges[E++]={{it.f.f,it.f.s},it.s};
    edges[E++]={{it.f.s,it.f.f},it.s};
  }
  mp.clear();
  sort(edges,edges+E);
  for (int i=0;i<E;i++){
    L[edges[i].f.f]=min(L[edges[i].f.f],i);
    R[edges[i].f.f]=max(R[edges[i].f.f],i);
  }
  for (int i=1;i<=N;i++)
    if (vis[i]==0){ 
      //cout<<"Component: "<<i<<endl;
      C=0;
      findCycle(i,i);
      /*
      cout<<"Cycle: ";
      for (int i=0;i<C;i++)
      	cout<<cycle[i]<<' '<<adjDis[i]<<endl;;
      cout<<endl;
      */
      if (C==0){
	//cout<<"multiEdge: "<<findDiameter(i)<<endl;
	ans+=findDiameter(i);
	continue;
      }
      maxCur=0;
      for (int i=0;i<C;i++){
	pref[i]=0;
	suff[i]=0;
	int inFront=cycle[(i+1)%C];
	int inBack=cycle[(i-1+C)%C];
	//adjDis[i]=mp[{min(cycle[i],inFront),max(cycle[i],inFront)}];
	bad=inFront;
	bad2=inBack;
	maxCur=max(maxCur,findDiameter(cycle[i]));
	findFarthest(cycle[i],cycle[i],0);
	deepest[i]=maxDis;
      }
      ll temp=0,temp2=0;
      for (int i=0;i<C;i++){
	if (i>0){
	  pref[i]=temp+adjDis[i-1];
	  temp=pref[i];
	  pref[i]=max(temp2,pref[i]+deepest[i]);
	  temp2=pref[i];
	}
	else{
	  pref[i]=deepest[i];
	  temp2=pref[i];
	}
      }
      /*
      cout<<"deepest: "<<' ';
      for (int x:deepest)
	cout<<x<<' ';
      cout<<endl;
      cout<<"adjDis: "<<' ';
      for (int x:adjDis)
	cout<<x<<' ';
      cout<<endl;
      cout<<"pref: ";
      for (int i=0;i<C;i++)
	cout<<pref[i]<<' ';
      cout<<endl;
      */
      temp=0; temp2=0;
      for (int i=C-1;i>=0;i--){
	if (i+1<C){
	  suff[i]=temp+adjDis[i];
	  temp=suff[i];
	  suff[i]=max(temp2,suff[i]+deepest[i]);
	  temp2=suff[i];
	}
	else{
	  suff[i]=deepest[i];
	  temp2=suff[i];
	}
      }
      for (int i=0;i+1<C;i++){
	//cout<<i<<": "<<adjDis.back()<<' '<<pref2[i]<<' '<<suff2[i+1]<<endl;
	maxCur=max(maxCur,adjDis[C-1]+pref[i]+suff[i+1]);
      }
      ll sweep=0;
      for (int i=0;i<C;i++){
	maxCur=max(maxCur,sweep+deepest[i]);
	sweep=max(sweep,(ll)deepest[i]);
	sweep+=adjDis[i];
      }
      ans+=maxCur;
      //cout<<"maxCur: "<<maxCur<<endl;
    }
  printf("%lld\n",ans);
}

Compilation message

islands.cpp:1:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/STACK: 2000000")
 
islands.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("O3")
 
islands.cpp:4:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("unroll-loops")
 
islands.cpp: In function 'int main()':
islands.cpp:91:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&N);
   ~~~~~^~~~~~~~~
islands.cpp:95:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&Y,&L);
     ~~~~~^~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Runtime error 25 ms 16448 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 22 ms 16384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 22 ms 16384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 22 ms 16384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 22 ms 16384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 21 ms 16384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 21 ms 16384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 22 ms 16384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 22 ms 16384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 21 ms 16512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 21 ms 16512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
# Verdict Execution time Memory Grader output
1 Runtime error 26 ms 16512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 23 ms 16640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 36 ms 19328 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 65 ms 25848 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 174 ms 54596 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 322 ms 92572 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 1096 ms 131072 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 959 ms 131072 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -