oj.uz

Submission #793283

# Submission time Handle Problem Language Result Execution time Memory
793283 2023-07-25T17:18:19 Z MODDI Stations (IOI20_stations) C++17
100 / 100
 776 ms 808 KB 
#include <bits/stdc++.h>
#include "stations.h"
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
int cnt;
vector<int> G[1001], labels;
void dfs(int at, int p, int d){
	if(!d)	labels[at] = cnt++;
	for(auto next : G[at]){
		if(next != p)
			dfs(next, at, d^1);
	}
	if(d)	labels[at] = cnt++;
}
vector<int> label(int n, int k, vector<int> u, vector<int> v){
	cnt = 0;
	for(int i = 0; i < n; i++){
			G[i].clear();
	}
	for(int i = 0; i < n - 1; i++){
		G[u[i]].pb(v[i]);
		G[v[i]].pb(u[i]);
	}
	labels.resize(n);
	dfs(0, -1, 0);
	return labels;
}
int find_next_station(int s, int t, vector<int> c){
	if(s < c[0]){
		if(t < s ||  t >= c.back())	return c.back();
		return *lower_bound(c.begin(), c.end(), t);
	}
	if(t > s || t <= c[0])	return c[0];
	return *--upper_bound(c.begin(), c.end(), t);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 450 ms 548 KB Output is correct
2 Correct 304 ms 672 KB Output is correct
3 Correct 678 ms 420 KB Output is correct
4 Correct 557 ms 532 KB Output is correct
5 Correct 506 ms 420 KB Output is correct
6 Correct 374 ms 520 KB Output is correct
7 Correct 367 ms 520 KB Output is correct
8 Correct 3 ms 492 KB Output is correct
9 Correct 4 ms 492 KB Output is correct
10 Correct 0 ms 500 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 361 ms 536 KB Output is correct
2 Correct 493 ms 544 KB Output is correct
3 Correct 723 ms 420 KB Output is correct
4 Correct 555 ms 416 KB Output is correct
5 Correct 531 ms 532 KB Output is correct
6 Correct 389 ms 520 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 345 ms 680 KB Output is correct
2 Correct 291 ms 676 KB Output is correct
3 Correct 621 ms 528 KB Output is correct
4 Correct 589 ms 420 KB Output is correct
5 Correct 446 ms 528 KB Output is correct
6 Correct 416 ms 568 KB Output is correct
7 Correct 416 ms 528 KB Output is correct
8 Correct 2 ms 500 KB Output is correct
9 Correct 4 ms 488 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 519 ms 528 KB Output is correct
12 Correct 465 ms 708 KB Output is correct
13 Correct 411 ms 748 KB Output is correct
14 Correct 411 ms 536 KB Output is correct
15 Correct 50 ms 420 KB Output is correct
16 Correct 44 ms 600 KB Output is correct
17 Correct 67 ms 528 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 658 ms 568 KB Output is correct
2 Correct 451 ms 528 KB Output is correct
3 Correct 572 ms 420 KB Output is correct
4 Correct 1 ms 500 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 1 ms 496 KB Output is correct
7 Correct 596 ms 524 KB Output is correct
8 Correct 691 ms 596 KB Output is correct
9 Correct 494 ms 532 KB Output is correct
10 Correct 572 ms 508 KB Output is correct
11 Correct 4 ms 500 KB Output is correct
12 Correct 5 ms 608 KB Output is correct
13 Correct 5 ms 500 KB Output is correct
14 Correct 2 ms 492 KB Output is correct
15 Correct 2 ms 492 KB Output is correct
16 Correct 512 ms 416 KB Output is correct
17 Correct 404 ms 524 KB Output is correct
18 Correct 478 ms 524 KB Output is correct
19 Correct 424 ms 416 KB Output is correct
20 Correct 376 ms 528 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 369 ms 660 KB Output is correct
2 Correct 432 ms 656 KB Output is correct
3 Correct 680 ms 416 KB Output is correct
4 Correct 569 ms 532 KB Output is correct
5 Correct 524 ms 416 KB Output is correct
6 Correct 456 ms 660 KB Output is correct
7 Correct 403 ms 544 KB Output is correct
8 Correct 2 ms 496 KB Output is correct
9 Correct 3 ms 492 KB Output is correct
10 Correct 0 ms 492 KB Output is correct
11 Correct 336 ms 548 KB Output is correct
12 Correct 490 ms 544 KB Output is correct
13 Correct 776 ms 532 KB Output is correct
14 Correct 496 ms 416 KB Output is correct
15 Correct 427 ms 524 KB Output is correct
16 Correct 371 ms 524 KB Output is correct
17 Correct 502 ms 508 KB Output is correct
18 Correct 429 ms 528 KB Output is correct
19 Correct 342 ms 808 KB Output is correct
20 Correct 289 ms 532 KB Output is correct
21 Correct 42 ms 492 KB Output is correct
22 Correct 63 ms 544 KB Output is correct
23 Correct 89 ms 620 KB Output is correct
24 Correct 5 ms 492 KB Output is correct
25 Correct 4 ms 492 KB Output is correct
26 Correct 4 ms 492 KB Output is correct
27 Correct 3 ms 488 KB Output is correct
28 Correct 1 ms 492 KB Output is correct
29 Correct 451 ms 420 KB Output is correct
30 Correct 333 ms 532 KB Output is correct
31 Correct 462 ms 416 KB Output is correct
32 Correct 391 ms 416 KB Output is correct
33 Correct 387 ms 420 KB Output is correct
34 Correct 231 ms 592 KB Output is correct
35 Correct 402 ms 760 KB Output is correct
36 Correct 463 ms 652 KB Output is correct
37 Correct 354 ms 740 KB Output is correct
38 Correct 404 ms 668 KB Output is correct
39 Correct 301 ms 628 KB Output is correct
40 Correct 442 ms 752 KB Output is correct
41 Correct 383 ms 736 KB Output is correct
42 Correct 43 ms 544 KB Output is correct
43 Correct 115 ms 616 KB Output is correct
44 Correct 120 ms 528 KB Output is correct
45 Correct 178 ms 604 KB Output is correct
46 Correct 197 ms 596 KB Output is correct
47 Correct 293 ms 628 KB Output is correct
48 Correct 53 ms 752 KB Output is correct
49 Correct 52 ms 676 KB Output is correct