oj.uz

Submission #741109

# Submission time Handle Problem Language Result Execution time Memory
741109 2023-05-13T14:35:33 Z siewjh Stations (IOI20_stations) C++17
100 / 100
 1009 ms 824 KB 
#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
vector<int> adj[MAXN], lbls;
int ind;
 
void dfs(int x, int par, bool typ){
    if (typ) lbls[x] = ++ind;
    for (int nxt : adj[x]){
        if (nxt == par) continue;
        dfs(nxt, x, !typ);
    }
    if (!typ) lbls[x] = ++ind;
}
 
vector<int> label(int nodes, int maxlbl, vector<int> u, vector<int> v) {
	for (int i = 0; i < nodes; i++) adj[i].clear();
	for (int i = 0; i < nodes - 1; i++){
        int a = u[i], b = v[i];
        adj[a].push_back(b);
        adj[b].push_back(a);
	}
	lbls = vector<int>(nodes, -1);
	ind = -1;
	dfs(0, -1, 1);
	return lbls;
}
 
int find_next_station(int s, int t, vector<int> c) {
    if (s < c[0]){
        if (t < s || t > c.back()) return c.back();
        else return *lower_bound(c.begin(), c.end(), t);
    }
    else{
        if (t > s || t < c[0]) return c[0];
        else return *(upper_bound(c.begin(), c.end(), t) - 1);
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 534 ms 656 KB Output is correct
2 Correct 397 ms 672 KB Output is correct
3 Correct 891 ms 416 KB Output is correct
4 Correct 638 ms 544 KB Output is correct
5 Correct 557 ms 416 KB Output is correct
6 Correct 481 ms 548 KB Output is correct
7 Correct 408 ms 556 KB Output is correct
8 Correct 2 ms 488 KB Output is correct
9 Correct 5 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 516 ms 504 KB Output is correct
2 Correct 584 ms 528 KB Output is correct
3 Correct 953 ms 416 KB Output is correct
4 Correct 694 ms 420 KB Output is correct
5 Correct 643 ms 544 KB Output is correct
6 Correct 477 ms 528 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 529 ms 668 KB Output is correct
2 Correct 471 ms 676 KB Output is correct
3 Correct 1009 ms 576 KB Output is correct
4 Correct 741 ms 416 KB Output is correct
5 Correct 605 ms 532 KB Output is correct
6 Correct 479 ms 548 KB Output is correct
7 Correct 513 ms 540 KB Output is correct
8 Correct 1 ms 500 KB Output is correct
9 Correct 2 ms 516 KB Output is correct
10 Correct 0 ms 492 KB Output is correct
11 Correct 622 ms 524 KB Output is correct
12 Correct 433 ms 656 KB Output is correct
13 Correct 442 ms 752 KB Output is correct
14 Correct 488 ms 544 KB Output is correct
15 Correct 41 ms 444 KB Output is correct
16 Correct 69 ms 548 KB Output is correct
17 Correct 118 ms 544 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 904 ms 536 KB Output is correct
2 Correct 517 ms 524 KB Output is correct
3 Correct 596 ms 528 KB Output is correct
4 Correct 2 ms 500 KB Output is correct
5 Correct 5 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 505 ms 416 KB Output is correct
8 Correct 783 ms 416 KB Output is correct
9 Correct 707 ms 432 KB Output is correct
10 Correct 701 ms 420 KB Output is correct
11 Correct 6 ms 492 KB Output is correct
12 Correct 6 ms 492 KB Output is correct
13 Correct 4 ms 488 KB Output is correct
14 Correct 3 ms 492 KB Output is correct
15 Correct 2 ms 492 KB Output is correct
16 Correct 548 ms 420 KB Output is correct
17 Correct 541 ms 416 KB Output is correct
18 Correct 533 ms 532 KB Output is correct
19 Correct 618 ms 520 KB Output is correct
20 Correct 435 ms 420 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 556 ms 672 KB Output is correct
2 Correct 490 ms 644 KB Output is correct
3 Correct 898 ms 420 KB Output is correct
4 Correct 752 ms 416 KB Output is correct
5 Correct 658 ms 416 KB Output is correct
6 Correct 455 ms 540 KB Output is correct
7 Correct 435 ms 532 KB Output is correct
8 Correct 3 ms 492 KB Output is correct
9 Correct 4 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 423 ms 536 KB Output is correct
12 Correct 503 ms 744 KB Output is correct
13 Correct 915 ms 416 KB Output is correct
14 Correct 666 ms 508 KB Output is correct
15 Correct 595 ms 420 KB Output is correct
16 Correct 483 ms 548 KB Output is correct
17 Correct 701 ms 516 KB Output is correct
18 Correct 500 ms 628 KB Output is correct
19 Correct 453 ms 640 KB Output is correct
20 Correct 474 ms 528 KB Output is correct
21 Correct 62 ms 492 KB Output is correct
22 Correct 74 ms 576 KB Output is correct
23 Correct 99 ms 588 KB Output is correct
24 Correct 6 ms 496 KB Output is correct
25 Correct 6 ms 492 KB Output is correct
26 Correct 4 ms 492 KB Output is correct
27 Correct 5 ms 508 KB Output is correct
28 Correct 2 ms 492 KB Output is correct
29 Correct 484 ms 420 KB Output is correct
30 Correct 561 ms 416 KB Output is correct
31 Correct 548 ms 528 KB Output is correct
32 Correct 499 ms 424 KB Output is correct
33 Correct 575 ms 420 KB Output is correct
34 Correct 323 ms 544 KB Output is correct
35 Correct 453 ms 540 KB Output is correct
36 Correct 508 ms 624 KB Output is correct
37 Correct 471 ms 648 KB Output is correct
38 Correct 513 ms 708 KB Output is correct
39 Correct 507 ms 624 KB Output is correct
40 Correct 453 ms 668 KB Output is correct
41 Correct 450 ms 756 KB Output is correct
42 Correct 66 ms 548 KB Output is correct
43 Correct 101 ms 672 KB Output is correct
44 Correct 112 ms 532 KB Output is correct
45 Correct 176 ms 544 KB Output is correct
46 Correct 318 ms 524 KB Output is correct
47 Correct 304 ms 520 KB Output is correct
48 Correct 56 ms 656 KB Output is correct
49 Correct 61 ms 824 KB Output is correct