Submission #392450

#	Time	Username	Problem	Language	Result	Execution time	Memory
392450		kshitij_sodani	Rail (IOI14_rail)	C++14	30 / 100	167 ms	98368 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<int> ss;
	vector<int> ee;
	//cout<<mi.a<<":"<<mi.b<<endl;
	int ne=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(2*xx<it[0][i]){
					bb[i]=1;
					vis[i]=1;
					aa[i]=aa[0]+mi.a-xx;
				}
				else{
					ee.pb(i);
					yy++;
				}
				continue;
			}
			else{
				ss.pb(i);
			}
		}
		else if(mi.b==i){
			aa[i]=it[0][i]+aa[0];

		}
	}
	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[0][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;
*/



}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:38:6: warning: unused variable 'cur' [-Wunused-variable]
   38 |  int cur=0;
      |      ^~~

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