Submission #392912

#	Time	Username	Problem	Language	Result	Execution time	Memory
392912		kshitij_sodani	Rail (IOI14_rail)	C++14	100 / 100	143 ms	98500 KiB

rail

//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n'

#include "rail.h"

int it[5001][5001];
int vis[5001];
int getdistance(int i,int j){
	if(it[i][j]==-1){
		it[i][j]=getDistance(i,j);
		return it[i][j];
	}
	else{
		return it[i][j];
	}
}
void findLocation(int n, int x, int aa[], int bb[])
{
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			it[i][j]=-1;
		}
	}

	aa[0]=x;
	bb[0]=1;
	for(int i=1;i<n;i++){
		bb[i]=2;
	}
	vis[0]=1;
//	int cur=0;

	pair<int,int> mi;
	mi.b=-1;
	for(int i=0;i<n;i++){
		if(vis[i]==0){
			getdistance(0,i);
			if(mi.b==-1){
				mi={it[0][i],i};
			}
			else{
				mi=min(mi,{it[0][i],i});
			}
		}
	}

	int yy=0;
	vector<pair<int,int>> ss;
	vector<pair<int,int>> ee;
	//cout<<mi.a<<":"<<mi.b<<endl;
	int ne=mi.b;
	it[mi.b][0]=it[0][mi.b];
	for(int i=1;i<n;i++){
		if(mi.b!=i){
			int xx=getdistance(mi.b,i);
			if(it[0][i]==mi.a+xx){
				if(xx<it[0][mi.b]){
					bb[i]=1;
					vis[i]=1;
					aa[i]=aa[0]+mi.a-xx;
				}
				else{
					ee.pb({it[mi.b][i],i});
					yy++;
				}
				continue;
			}
			else{
				ss.pb({it[0][i],i});
			}
		}
		else if(mi.b==i){
			aa[i]=it[0][i]+aa[0];
		}
	}

	sort(ss.begin(),ss.end());
	//reverse(ss.begin(),ss.end());
	/*for(auto j:ss){
		cout<<j.a<<".."<<j.b<<endl;
	}*/
	sort(ee.begin(),ee.end());
	//reverse(ee.begin(),ee.end());
	vector<pair<int,int>> zz;
	int cur=mi.b;
	map<int,int> ac;
	ac[aa[mi.b]]++;
	for(auto j:ss){
		getdistance(0,j.b);
		getdistance(0,cur);
		int x=getdistance(cur,j.b);
		int z=it[0][cur]+x-it[0][j.b];
		
		if(ac.find(aa[cur]-(z/2))!=ac.end()){
			aa[j.b]=aa[cur]-x;
			bb[j.b]=1;
		}
		else{
			aa[j.b]=aa[0]+it[0][j.b];
			ac[aa[j.b]]++;
			cur=j.b;
		}
	/*	if(x<it[0][cur]){
			aa[j.b]=aa[cur]-x;
			bb[j.b]=1;
		}
		else{
			aa[j.b]=aa[0]+it[0][j.b];
			cur=j.b;
		}*/
	}
	ac.clear();
	ac[aa[0]]++;



	cur=0;
	for(auto j:ee){
		getdistance(mi.b,j.b);
		getdistance(mi.b,cur);
		int x=getdistance(cur,j.b);
		int z=it[mi.b][cur]+x-it[mi.b][j.b];
		//cout<<j.b<<":"<<z<<endl;
	//	cout<<cur<<endl;
		//cout<<it[mi.b][cur]<<",,"<<it[cur][j.b]<<",,"<<it[mi.b][j.b]<<endl;
		if(ac.find(aa[cur]+(z/2))!=ac.end()){
			aa[j.b]=aa[cur]+x;

		}
		else{
			aa[j.b]=aa[mi.b]-it[mi.b][j.b];
			ac[aa[j.b]]++;
			bb[j.b]=1;
			cur=j.b;
		}
	/*	if(x<it[0][cur]){
			aa[j.b]=aa[cur]-x;
			bb[j.b]=1;
		}
		else{
			aa[j.b]=aa[0]+it[0][j.b];
			cur=j.b;
		}*/
	}

	/*while(ss.size()){
		if(ss.size()==1){
			aa[ss.back().b]=aa[0]+it[0][ss.back().b];
			//bb[ss.back().b]=2;
			break;
		}
		int x=getdistance(ss[ss.size()-2].b,ss[ss.size()-1].b);
		if(x+it[0][ss[ss.size()-2].b]==it[0][ss[ss.size()-1].b]){
			zz.pb({ss[ss.size()-2].b,ss[ss.size()-1].b});
			bb[ss.back().b]=1;
			cout<<ss.back().a<<"<"<<ss.back().b<<endl;
		}
		else{
			aa[ss.back().b]=aa[0]+it[0][ss.back().b];
		
		}
		ss.pop_back();
	}
	reverse(zz.begin(),zz.end());
	for(auto j:zz){
		cout<<j.a<<"::"<<j.b<<endl;
	}
	while(zz.size()){
		aa[zz.back().b]=aa[zz.back().a]-it[zz.back().a][zz.back().b];
		zz.pop_back();
	}
	//cout<<bb[mi.b]<<endl;
	while(ee.size()){
		if(ee.size()==1){
			aa[ee.back().b]=aa[mi.b]-it[mi.b][ee.back().b];
			bb[ee.back().b]=1;
			break;
		}
		int x=getdistance(ee[ee.size()-2].b,ee[ee.size()-1].b);
		if(x+it[mi.b][ee[ee.size()-2].b]==it[mi.b][ee[ee.size()-1].b]){
			zz.pb({ee[ee.size()-2].b,ee[ee.size()-1].b});
			
		}
		else{
			aa[ee.back().b]=aa[mi.b]-it[mi.b][ee.back().b];
			//cout<<ee.back().b<<endl;
			bb[ee.back().b]=1;
		}
		ee.pop_back();
	}
	reverse(zz.begin(),zz.end());
	while(zz.size()){
		aa[zz.back().b]=aa[zz.back().a]+it[zz.back().a][zz.back().b];
		zz.pop_back();
	}*/






/*	while(ss.size()){
		mi={0,0};
		mi.b=-1;
		for(auto i:ss){
			getdistance(0,i);
			if(mi.b==-1){
				mi={it[0][i],i};
			}
			else{
				mi=min(mi,{it[0][i],i});
			}
		}
		vector<int> tt;
		for(auto i:ss){
			if(mi.b!=i){
				int xx=getDistance(mi.b,i);
				if(it[0][i]==mi.a+xx){
					bb[i]=1;
					vis[i]=1;
					aa[i]=aa[0]+mi.a-xx;
					continue;
				}
				else{
					tt.pb(i);
				}
			}
			else if(mi.b==i){
				aa[i]=it[0][i]+aa[0];
			}
		}
		ss=tt;
	}
	if(ee.size()){
		mi.b=-1;
		for(auto i:ee){
			getdistance(ne,i);
			if(mi.b==-1){
				mi={it[ne][i],i};
			}
			else{
				mi=min(mi,{it[ne][i],i});
			}
		}
		ss.clear();
		for(auto i:ee){
			if(mi.b!=i){
				int xx=getDistance(mi.b,i);
				if(it[ne][i]==mi.a+xx){
					vis[i]=1;
					aa[i]=aa[ne]-mi.a+xx;
					continue;
				}
				else{
					ss.pb(i);
				}
			}
			else if(mi.b==i){
				bb[i]=1;
				aa[i]=-it[ne][i]+aa[ne];
			}
		}

		while(ss.size()){
			mi={0,0};
			mi.b=-1;
			for(auto i:ss){
				getdistance(ne,i);
				if(mi.b==-1){
					mi={it[ne][i],i};
				}
				else{
					mi=min(mi,{it[ne][i],i});
				}
			}
			vector<int> tt;
			for(auto i:ss){
				if(mi.b!=i){
					int xx=getDistance(mi.b,i);
					if(it[ne][i]==mi.a+xx){
						vis[i]=1;
						aa[i]=aa[ne]-(mi.a-xx);
						continue;
					}
					else{
						tt.pb(i);
					}
				}
				else if(mi.b==i){
					bb[i]=1;
					aa[i]=-it[ne][i]+aa[ne];
				}
			}
			ss=tt;
		}
	}
*/
	/*
	for(int i=0;i<n;i++){
		cout<<aa[i]<<":";
	}
	cout<<endl;
	for(int i=0;i<n;i++){
		cout<<bb[i]<<":";
	}
	cout<<endl;
*/



}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:58:6: warning: unused variable 'ne' [-Wunused-variable]
   58 |  int ne=mi.b;
      |      ^~

• Subtask 1: 8 / 8
• Subtask 2: 22 / 22
• Subtask 3: 26 / 26
• Subtask 4: 44 / 44