oj.uz

Submission #233052

# Submission time Handle Problem Language Result Execution time Memory
233052 2020-05-19T03:51:45 Z FieryPhoenix Islands (IOI08_islands) C++11
80 / 100
 1706 ms 131076 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]==1 && 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()){
    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:90:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&N);
   ~~~~~^~~~~~~~~
islands.cpp:94:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&Y,&L);
     ~~~~~^~~~~~~~~~~~~~

Subtask #1
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 512 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 640 KB Output is correct
2 Correct 9 ms 896 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2176 KB Output is correct
2 Correct 38 ms 5112 KB Output is correct
3 Correct 26 ms 2688 KB Output is correct
4 Correct 14 ms 1536 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 7032 KB Output is correct
2 Correct 83 ms 12536 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 23544 KB Output is correct
2 Correct 200 ms 27720 KB Output is correct
3 Correct 237 ms 37368 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 320 ms 39804 KB Output is correct
2 Correct 436 ms 66680 KB Output is correct
3 Correct 520 ms 76696 KB Output is correct
4 Correct 631 ms 92152 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 995 ms 111064 KB Output is correct
2 Runtime error 1706 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

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