oj.uz

Submission #926939

# Submission time Handle Problem Language Result Execution time Memory
926939 2024-02-14T05:28:38 Z daoquanglinh2007 Stations (IOI20_stations) C++17
100 / 100
 518 ms 1452 KB 
#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
 
#define isz(a) (int)(a).size()
 
const int NM = 1000;
 
vector <int> adj[NM+5];
int dep[NM+5];
int timer = 0, tin[NM+5], tout[NM+5];
vector <int> arr;
 
void dfs(int u, int p){
	dep[u] = (p == -1 ? 0 : dep[p]+1);
	tin[u] = ++timer;
	for (int v : adj[u]){
		if (v == p) continue;
		dfs(v, u);
	}
	tout[u] = ++timer;
}
 
vector <int> label(int n, int k, vector <int> u, vector <int> v){
	for (int i = 0; i < n; i++) adj[i].clear();
	for (int i = 0; i < n-1; i++){
		adj[u[i]].push_back(v[i]);
		adj[v[i]].push_back(u[i]);
	}
	dfs(0, -1);
	arr.clear();
	for (int i = 0; i < n; i++){
		if (dep[i]&1) arr.push_back(tout[i]); else arr.push_back(tin[i]);
	}
	sort(arr.begin(), arr.end());
	vector <int> ans(n);
	for (int i = 0; i < n; i++){
		if (dep[i]&1) ans[i] = lower_bound(arr.begin(), arr.end(), tout[i])-arr.begin();
		else ans[i] = lower_bound(arr.begin(), arr.end(), tin[i])-arr.begin();
	}
	return ans;
}
 
int find_next_station(int s, int t, vector <int> c){
	if (s < c.front()){
		if (t < s || t >= c.back()) return c.back();
		for (int i = 0; i < isz(c); i++)
			if (c[i] >= t) return c[i];
		return -1;
	}
	else{
		if (t <= c.front() || t > s) return c.front();
		for (int i = isz(c)-1; i >= 0; i--)
			if (c[i] <= t) return c[i];
		return -1;
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 336 ms 916 KB Output is correct
2 Correct 251 ms 928 KB Output is correct
3 Correct 512 ms 796 KB Output is correct
4 Correct 370 ms 684 KB Output is correct
5 Correct 342 ms 684 KB Output is correct
6 Correct 253 ms 908 KB Output is correct
7 Correct 303 ms 684 KB Output is correct
8 Correct 1 ms 772 KB Output is correct
9 Correct 3 ms 768 KB Output is correct
10 Correct 0 ms 768 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 952 KB Output is correct
2 Correct 323 ms 820 KB Output is correct
3 Correct 470 ms 684 KB Output is correct
4 Correct 362 ms 684 KB Output is correct
5 Correct 345 ms 684 KB Output is correct
6 Correct 261 ms 684 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 916 KB Output is correct
2 Correct 250 ms 924 KB Output is correct
3 Correct 508 ms 684 KB Output is correct
4 Correct 375 ms 684 KB Output is correct
5 Correct 329 ms 936 KB Output is correct
6 Correct 269 ms 900 KB Output is correct
7 Correct 242 ms 940 KB Output is correct
8 Correct 1 ms 768 KB Output is correct
9 Correct 2 ms 764 KB Output is correct
10 Correct 0 ms 768 KB Output is correct
11 Correct 338 ms 684 KB Output is correct
12 Correct 274 ms 1124 KB Output is correct
13 Correct 248 ms 1288 KB Output is correct
14 Correct 244 ms 684 KB Output is correct
15 Correct 27 ms 768 KB Output is correct
16 Correct 33 ms 940 KB Output is correct
17 Correct 63 ms 972 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 504 ms 684 KB Output is correct
2 Correct 360 ms 692 KB Output is correct
3 Correct 332 ms 684 KB Output is correct
4 Correct 1 ms 768 KB Output is correct
5 Correct 2 ms 768 KB Output is correct
6 Correct 0 ms 768 KB Output is correct
7 Correct 315 ms 684 KB Output is correct
8 Correct 518 ms 684 KB Output is correct
9 Correct 365 ms 688 KB Output is correct
10 Correct 314 ms 684 KB Output is correct
11 Correct 2 ms 764 KB Output is correct
12 Correct 3 ms 764 KB Output is correct
13 Correct 3 ms 768 KB Output is correct
14 Correct 3 ms 768 KB Output is correct
15 Correct 1 ms 768 KB Output is correct
16 Correct 271 ms 684 KB Output is correct
17 Correct 258 ms 684 KB Output is correct
18 Correct 284 ms 684 KB Output is correct
19 Correct 286 ms 684 KB Output is correct
20 Correct 271 ms 684 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 908 KB Output is correct
2 Correct 259 ms 916 KB Output is correct
3 Correct 511 ms 684 KB Output is correct
4 Correct 348 ms 684 KB Output is correct
5 Correct 316 ms 684 KB Output is correct
6 Correct 272 ms 920 KB Output is correct
7 Correct 240 ms 936 KB Output is correct
8 Correct 1 ms 764 KB Output is correct
9 Correct 2 ms 764 KB Output is correct
10 Correct 0 ms 768 KB Output is correct
11 Correct 242 ms 880 KB Output is correct
12 Correct 303 ms 856 KB Output is correct
13 Correct 512 ms 688 KB Output is correct
14 Correct 401 ms 684 KB Output is correct
15 Correct 320 ms 684 KB Output is correct
16 Correct 271 ms 940 KB Output is correct
17 Correct 329 ms 684 KB Output is correct
18 Correct 262 ms 1148 KB Output is correct
19 Correct 260 ms 1284 KB Output is correct
20 Correct 246 ms 684 KB Output is correct
21 Correct 32 ms 768 KB Output is correct
22 Correct 36 ms 932 KB Output is correct
23 Correct 66 ms 884 KB Output is correct
24 Correct 3 ms 768 KB Output is correct
25 Correct 3 ms 768 KB Output is correct
26 Correct 2 ms 764 KB Output is correct
27 Correct 2 ms 764 KB Output is correct
28 Correct 0 ms 768 KB Output is correct
29 Correct 269 ms 684 KB Output is correct
30 Correct 275 ms 720 KB Output is correct
31 Correct 271 ms 684 KB Output is correct
32 Correct 297 ms 684 KB Output is correct
33 Correct 282 ms 684 KB Output is correct
34 Correct 184 ms 1168 KB Output is correct
35 Correct 219 ms 1144 KB Output is correct
36 Correct 248 ms 1028 KB Output is correct
37 Correct 245 ms 1164 KB Output is correct
38 Correct 263 ms 1012 KB Output is correct
39 Correct 262 ms 1404 KB Output is correct
40 Correct 246 ms 1016 KB Output is correct
41 Correct 279 ms 1148 KB Output is correct
42 Correct 36 ms 896 KB Output is correct
43 Correct 64 ms 944 KB Output is correct
44 Correct 87 ms 896 KB Output is correct
45 Correct 98 ms 920 KB Output is correct
46 Correct 185 ms 864 KB Output is correct
47 Correct 201 ms 888 KB Output is correct
48 Correct 28 ms 1192 KB Output is correct
49 Correct 39 ms 1452 KB Output is correct