oj.uz

Submission #114441

# Submission time Handle Problem Language Result Execution time Memory
114441 2019-06-01T10:40:25 Z tjd229 Rail (IOI14_rail) C++14
100 / 100
 157 ms 78584 KB 
#include <stdio.h>
#include "rail.h"
#include <vector>
#include <algorithm>
#define pii pair<int,int>
using namespace std;
int d[5000][5000];
int call;
int getDist(int i,int j) {
	if (i == j) return 0;
	if (!d[i][j])
		d[i][j] = d[j][i] = getDistance(i, j), ++call;
	return d[i][j];
}
void findLocation(int N, int first, int location[], int stype[])
{
	int i; location[0] = first; stype[0] = 1;	
	vector<pii > v; int rc=0;
	int fi = 0; int mn = 1e9;
	for (i = 1; i < N; ++i) {
		int d = getDist(0, i);
		if (mn > d) {
			mn = d; 
			fi = i;
		}
	}
	location[fi] = first + mn;
	stype[fi] = 2;
	for (i = 1; i < N; ++i) {//find closest C
		if (i == fi) continue;
		int dist = getDist(fi,i);
		if (getDist(0, i) > dist && dist < getDist(0, fi)
			&& getDist(0, i) - getDist(0, fi) == dist) {			
			stype[i] = 1;
			location[i] = location[fi] - dist;
			if (location[rc] < location[i]) rc = i;			
		}
		else v.push_back({getDist(i,0),i});
		
	}
	sort(v.begin(), v.end());
	vector<pii > left = { {-location[rc],rc} };
	vector<pii >right = { {location[fi],fi} }; //coord,ix
	for (auto p : v) {
		int last = call;
		int x = p.second;
		d[rc][x] = d[x][rc] = getDist(0, x) - (location[rc]-location[0]);
		//printf("x:%d,%d\n", x,d[rc][x]);
		if (getDist(rc, x) < getDist(x, fi)) {
			int r = right.back().second;
			int pred = location[r]-getDist(r,x);
			if (pred > first) {
				pii p = {pred,10000};
				auto lb = upper_bound(right.begin(),right.end(),p);
				int nr = lb->second;
				d[nr][x] = d[x][nr] = getDist(r,x)-(location[r]-location[nr]);

				r = nr;
			}
			//init case && inner condi.
			if (r !=fi && getDist(rc, x) == getDist(x, r) + getDist(rc, r)) {
				stype[x] = 1;
				location[x] = pred;
			}
			else {
				stype[x] = 2;
				location[x] = location[rc]+getDist(rc,x);
				right.push_back({location[x],x});
			}
		}
		else {
			int l = left.back().second;
			int pred = location[l] + getDist(l,x);
			if (pred < first) {
				pii p = {-pred,10000};
				auto lb = upper_bound(left.begin(), left.end(), p);
				int nl = lb->second;
				d[nl][x] = d[x][nl] = getDist(l, x) - (location[nl] - location[l]);
				l = nl;
			}
			if (l !=rc&& getDist(fi, x) == getDist(l, x) + getDist(fi, l)) {
				stype[x] = 2;
				location[x] = pred;
			}
			else {
				stype[x] = 1;
				location[x] = location[fi] - getDist(fi,x);
				left.push_back({-location[x],x});
			}
		}
	}
}

Compilation message

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:45:7: warning: unused variable 'last' [-Wunused-variable]
   int last = call;
       ^~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
22.0 / 22.0

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

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 65144 KB Output is correct
2 Correct 122 ms 60768 KB Output is correct
3 Correct 124 ms 68344 KB Output is correct
4 Correct 122 ms 67576 KB Output is correct
5 Correct 126 ms 67908 KB Output is correct
6 Correct 145 ms 78072 KB Output is correct
7 Correct 138 ms 75768 KB Output is correct
8 Correct 126 ms 62584 KB Output is correct
9 Correct 132 ms 74364 KB Output is correct
10 Correct 122 ms 60664 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 65136 KB Output is correct
2 Correct 128 ms 60780 KB Output is correct
3 Correct 123 ms 68216 KB Output is correct
4 Correct 119 ms 67448 KB Output is correct
5 Correct 138 ms 67960 KB Output is correct
6 Correct 128 ms 78072 KB Output is correct
7 Correct 131 ms 75840 KB Output is correct
8 Correct 121 ms 62584 KB Output is correct
9 Correct 128 ms 74360 KB Output is correct
10 Correct 143 ms 60600 KB Output is correct
11 Correct 121 ms 64632 KB Output is correct
12 Correct 147 ms 66552 KB Output is correct
13 Correct 126 ms 70520 KB Output is correct
14 Correct 157 ms 78584 KB Output is correct
15 Correct 124 ms 67996 KB Output is correct
16 Correct 130 ms 78584 KB Output is correct
17 Correct 123 ms 68216 KB Output is correct
18 Correct 121 ms 70012 KB Output is correct
19 Correct 119 ms 68512 KB Output is correct
20 Correct 116 ms 60372 KB Output is correct