oj.uz

Submission #159638

# Submission time Handle Problem Language Result Execution time Memory
159638 2019-10-23T16:18:21 Z Peacher29 Rail (IOI14_rail) C++14
100 / 100
 154 ms 60804 KB 
#include "rail.h"
#include<bits/stdc++.h>

using namespace std;

int dH[5000][5000];

int d(int i, int j){
	if(dH[i][j])
		return dH[i][j];
	return dH[i][j]=dH[j][i]=getDistance(i,j);
}

vector<pair<int,int>> pp;

map<int,int> irany; //hol - milyen
int hh[5000];
char c[5000];

void findLocation(int n, int first, int location[], int stype[])
{
	pp.resize(n-1);
	for(int i=0;i<n;i++){
		location[i]=0;
		stype[i]=0;
	}
	location[0]=first;
	stype[0]=1;
	irany[first]=1;
	for(int i=1;i<n;i++){
		pp[i-1]={d(i,0),i};
	}
	sort(pp.begin(),pp.end());
	int x = pp[0].second;
	location[x]=pp[0].first+first;
	irany[location[x]]=2;
	stype[x]=2;
	for(int i=0;i<n;i++){
		if(i!=0 && i!=x){
			if(d(0,i)==d(0,x)+d(x,i)){
				if(d(x,i)<d(0,x)){
					location[i]=location[x]-d(x,i);
					stype[i]=1;
					c[i]='.';
				} else {
					hh[i]=-1;
					c[i]='-';
				}
			} else {
				hh[i]=1;
				c[i]='+';
			}
		}
	}
	int L=x;
	for(pair<int,int>& p : pp){
		if(hh[p.second]==1){
			int k=p.second;
			int z = d(0,k)+d(L,k)-d(0,L);
			int hol = first+d(0,k)-z/2;
			auto it = irany.find(hol);
			if(it==irany.end() || it->second == 1){
				location[k]=first+d(0,k);
				stype[k]=2;
				irany[location[k]]=stype[k];
			} else {
				location[k]=location[L]-d(L,k);
				stype[k]=1;
				irany[location[k]]=stype[k];
			}
			if(location[k]>location[L]){
				L=k;
			}
		}
	}
	L=0;
	for(pair<int,int> p : pp){
		if(hh[p.second]==-1){
			int k=p.second;
			int z = d(x,k)+d(L,k)-d(x,L);
			int hol = location[x]-d(x,k)+z/2;
			auto it = irany.find(hol);
			if(it==irany.end() || it->second == 2){
				location[k]=location[x]-d(x,k);
				stype[k]=1;
				irany[location[k]]=stype[k];
			} else {
				location[k]=location[L]+d(L,k);
				stype[k]=2;
				irany[location[k]]=stype[k];
			}
			if(location[k]<location[L]){
				L=k;
			}
		}
	}
	//cout << "0\n"<<n<<"\n";
	//for(int i=0;i<n;i++) cout << stype[i] << " " << location[i] << " " << c[i] << endl;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
22.0 / 22.0

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

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 56440 KB Output is correct
2 Correct 139 ms 51472 KB Output is correct
3 Correct 144 ms 60792 KB Output is correct
4 Correct 146 ms 60536 KB Output is correct
5 Correct 143 ms 60552 KB Output is correct
6 Correct 144 ms 60408 KB Output is correct
7 Correct 145 ms 60152 KB Output is correct
8 Correct 138 ms 54264 KB Output is correct
9 Correct 140 ms 54904 KB Output is correct
10 Correct 138 ms 51448 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 56440 KB Output is correct
2 Correct 138 ms 51448 KB Output is correct
3 Correct 146 ms 60804 KB Output is correct
4 Correct 153 ms 60544 KB Output is correct
5 Correct 146 ms 60580 KB Output is correct
6 Correct 153 ms 60536 KB Output is correct
7 Correct 145 ms 60280 KB Output is correct
8 Correct 149 ms 54232 KB Output is correct
9 Correct 141 ms 55044 KB Output is correct
10 Correct 137 ms 51320 KB Output is correct
11 Correct 148 ms 56904 KB Output is correct
12 Correct 142 ms 58320 KB Output is correct
13 Correct 143 ms 60360 KB Output is correct
14 Correct 154 ms 60500 KB Output is correct
15 Correct 144 ms 60740 KB Output is correct
16 Correct 144 ms 60768 KB Output is correct
17 Correct 142 ms 60680 KB Output is correct
18 Correct 142 ms 60508 KB Output is correct
19 Correct 144 ms 60584 KB Output is correct
20 Correct 138 ms 51336 KB Output is correct