oj.uz

Submission #550887

# Submission time Handle Problem Language Result Execution time Memory
550887 2022-04-19T11:05:47 Z CSQ31 Rail (IOI14_rail) C++17
100 / 100
 114 ms 60692 KB 
#include <bits/stdc++.h>
#include "rail.h"
using namespace std;
int d[5001][5001];
int ask(int i,int j){
	if(i==j)return 0;
	if(d[i][j])return d[i][j];
	d[i][j] = d[j][i] = getDistance(i,j);
	return d[i][j];
}
void findLocation(int n, int f, int location[], int stype[])
{
	location[0] = f;
	stype[0] = 1;
	
	//find the closest guy to 0
	int mnn = 1e9;
	int x = 0;
	vector<int>l,r;
	for(int i=1;i<n;i++){
		if(mnn > ask(0,i)){
			mnn = ask(0,i);
			x = i;
		}
	}
	stype[x] = 2;
	location[x] = f + ask(0,x);
	for(int i=0;i<n;i++){
		if(i!=0 && i!=x){
			if(ask(0,i) == ask(0,x) + ask(x,i))l.push_back(i);
			else r.push_back(i);
		}
	}
	vector<pair<int,int>>a;
	for(int y:r)a.push_back({ask(0,y),y});
	sort(a.begin(),a.end());
	int last = x;
	map<int,bool>seen;
	for(auto Z : a){
		int z = Z.second;
		//try the path x->y->z
		//will always be a upper bound to x->z
		int m = ask(0,last) + ask(last,z);
		m-=ask(0,z);
		m/=2;
		if(location[last] - m>=0 && seen[location[last] - m]){
			stype[z] = 1;
			location[z] = location[last] - ask(last,z);
		}else{
			stype[z] = 2;
			location[z] = location[0] + ask(0,z);
			seen[location[z]] = 1;
			last = z;
		}
	}
	a.clear();
	seen.clear();
	for(int y:l)a.push_back({ask(x,y),y});
	sort(a.begin(),a.end());
	last = 0;
	for(auto Z : a){
		int z = Z.second;
		int m = ask(x,last) + ask(last,z);
		m-=ask(x,z);
		m/=2;
		if(location[last] + m <= 1000000 && seen[location[last] + m]){
			stype[z] = 2;
			location[z] = location[last] + ask(last,z);
		}else{
			stype[z] = 1;
			location[z] = location[x] - ask(x,z);
			last = z;
			seen[location[z]] = 1;
			
		}
	}
	
	
	//for(int i=0;i<n;i++)cout<<stype[i]<<" "<<location[i]<<'\n';
}

Subtask #1
8.0 / 8.0

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

Subtask #2
22.0 / 22.0

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

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 56268 KB Output is correct
2 Correct 95 ms 51320 KB Output is correct
3 Correct 94 ms 60548 KB Output is correct
4 Correct 96 ms 60288 KB Output is correct
5 Correct 94 ms 60424 KB Output is correct
6 Correct 93 ms 60692 KB Output is correct
7 Correct 97 ms 59980 KB Output is correct
8 Correct 89 ms 53872 KB Output is correct
9 Correct 90 ms 55040 KB Output is correct
10 Correct 94 ms 51020 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 56264 KB Output is correct
2 Correct 94 ms 51320 KB Output is correct
3 Correct 94 ms 60604 KB Output is correct
4 Correct 95 ms 60280 KB Output is correct
5 Correct 92 ms 60420 KB Output is correct
6 Correct 94 ms 60676 KB Output is correct
7 Correct 95 ms 60020 KB Output is correct
8 Correct 91 ms 53876 KB Output is correct
9 Correct 103 ms 55032 KB Output is correct
10 Correct 94 ms 50892 KB Output is correct
11 Correct 103 ms 56824 KB Output is correct
12 Correct 95 ms 58240 KB Output is correct
13 Correct 96 ms 60544 KB Output is correct
14 Correct 95 ms 60476 KB Output is correct
15 Correct 114 ms 60532 KB Output is correct
16 Correct 97 ms 60568 KB Output is correct
17 Correct 107 ms 60280 KB Output is correct
18 Correct 99 ms 60540 KB Output is correct
19 Correct 107 ms 60588 KB Output is correct
20 Correct 93 ms 51324 KB Output is correct