oj.uz

답안 #798142

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
798142 2023-07-30T11:50:44 Z QwertyPi 철로 (IOI14_rail) C++14
100 / 100
 97 ms 1456 KB 
#include "rail.h"
#include <bits/stdc++.h>
#define INF (1 << 30)
using namespace std;
 
int d0[5011], d1[5011];
 
map<pair<int, int>, int> M;
int sGetDistance(int i, int j){
	if(i > j) swap(i, j);
	if(i == j) return 0;
	if(M.count({i, j})) return M[{i, j}];
	return M[{i, j}] = getDistance(i, j);
}
void findLocation(int N, int first, int location[], int stype[]){
	for(int i = 1; i < N; i++) d0[i] = sGetDistance(0, i); int p0 = 0;
	int s = INF, p1; for(int i = 1; i < N; i++) if(d0[i] < s) s = d0[i], p1 = i;
	for(int i = 0; i < N; i++) if(i != p1) d1[i] = sGetDistance(p1, i);
	
	location[p0] = first; stype[p0] = 1;
	location[p1] = first + s; stype[p1] = 2;
	vector<int> L, R;
	for(int i = 0; i < N; i++){
		if(i != p0 && i != p1){
			if(d1[i] < s) location[i] = first + s - d1[i], stype[i] = 1;
			if(d0[i] - d1[i] == s) L.push_back(i);
			else R.push_back(i);
		}
	}
	sort(L.begin(), L.end(), [](int x, int y){ return d1[x] < d1[y]; });
	sort(R.begin(), R.end(), [](int x, int y){ return d0[x] < d0[y]; });
	int leftmost = p0;
	for(int l : L){
		int dis = sGetDistance(leftmost, l);
		location[l] = location[leftmost] + dis; stype[l] = 2;
		int leftBound = leftmost; for(int i = 0; i < N; i++) if(stype[i] == 1 && location[leftBound] <= location[i] && location[i] < location[l]) leftBound = i;
		if((location[leftBound] - location[leftmost]) * 2 == d1[leftmost] + dis - d1[l]){
			location[l] = location[leftmost] + dis; stype[l] = 2;
		}else{
			location[l] = location[p1] - d1[l]; stype[l] = 1;
			leftmost = l;
		}
	}
	
	int rightmost = p1;
	for(int r : R){
		int dis = sGetDistance(rightmost, r);
		location[r] = location[rightmost] - dis; stype[r] = 1;
		int rightBound = rightmost; for(int i = 0; i < N; i++) if(stype[i] == 2 && location[r] < location[i] && location[i] <= location[rightBound]) rightBound = i;
		if((location[rightmost] - location[rightBound]) * 2 == d0[rightmost] + dis - d0[r]){
			location[r] = location[rightmost] - dis; stype[r] = 1;
		}else{
			rightmost = r;
			location[r] = location[p0] + d0[r]; stype[r] = 2;
		}
	}
}

Compilation message

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:16:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   16 |  for(int i = 1; i < N; i++) d0[i] = sGetDistance(0, i); int p0 = 0;
      |  ^~~
rail.cpp:16:57: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   16 |  for(int i = 1; i < N; i++) d0[i] = sGetDistance(0, i); int p0 = 0;
      |                                                         ^~~
rail.cpp:24:14: warning: 'p1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   24 |   if(i != p0 && i != p1){
      |      ~~~~~~~~^~~~~~~~~~

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #2
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #3
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 72 ms 1456 KB Output is correct
2 Correct 74 ms 1368 KB Output is correct
3 Correct 73 ms 1360 KB Output is correct
4 Correct 82 ms 1352 KB Output is correct
5 Correct 83 ms 1356 KB Output is correct
6 Correct 74 ms 1356 KB Output is correct
7 Correct 97 ms 1384 KB Output is correct
8 Correct 75 ms 1436 KB Output is correct
9 Correct 90 ms 1372 KB Output is correct
10 Correct 80 ms 1356 KB Output is correct

Subtask #4
44.0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 96 ms 1364 KB Output is correct
2 Correct 97 ms 1420 KB Output is correct
3 Correct 74 ms 1456 KB Output is correct
4 Correct 81 ms 1360 KB Output is correct
5 Correct 79 ms 1448 KB Output is correct
6 Correct 74 ms 1356 KB Output is correct
7 Correct 75 ms 1384 KB Output is correct
8 Correct 75 ms 1356 KB Output is correct
9 Correct 74 ms 1452 KB Output is correct
10 Correct 75 ms 1356 KB Output is correct
11 Correct 72 ms 1364 KB Output is correct
12 Correct 72 ms 1360 KB Output is correct
13 Correct 74 ms 1356 KB Output is correct
14 Correct 83 ms 1368 KB Output is correct
15 Correct 76 ms 1356 KB Output is correct
16 Correct 72 ms 1364 KB Output is correct
17 Correct 71 ms 1360 KB Output is correct
18 Correct 74 ms 1352 KB Output is correct
19 Correct 77 ms 1364 KB Output is correct
20 Correct 78 ms 1352 KB Output is correct