oj.uz

Submission #416053

# Submission time Handle Problem Language Result Execution time Memory
416053 2021-06-01T21:07:59 Z SuhaibSawalha1 Stations (IOI20_stations) C++17
76 / 100
 1224 ms 808 KB 
#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
 
vector<vector<int>> adj;
vector<int> lab, in, out;
int dfst;
 
void dfs (int u = 0, int p = -1, int d = 0) {
	in[u] = dfst++;
	for (int v : adj[u]) {
		if (v ^ p) {
			dfs(v, u, d ^ 1);
		}
	}
	out[u] = dfst++;
	lab[u] = d ? in[u] : out[u];
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	adj.assign(n, {});
	lab.resize(n);
	in.resize(n);
	out.resize(n);
	dfst = 0;
	for (int i = 0; i < n - 1; ++i) {
		adj[u[i]].push_back(v[i]);
		adj[v[i]].push_back(u[i]);
	}
	dfs();
	return lab;
}

int find_next_station(int s, int t, vector<int> c) {
	if (c.size() == 1) {
		return c[0];
	}
	if (s < c[0]) { 
		if (t < s || t > c.back()) {
			return c.back();
		}
		return *lower_bound(c.begin(), c.end(), t);
	}
	else { 
		if (t > s || t < c[1]) {
			return c[0];
		}
		return *(upper_bound(c.begin(), c.end(), t) - 1);
	}
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 456 KB Invalid labels (values out of range). scenario=2, k=1000, vertex=0, label=1995
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 328 KB Invalid labels (values out of range). scenario=0, k=1000, vertex=0, label=1991
2 Halted 0 ms 0 KB -

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 680 ms 632 KB Output is correct
2 Correct 471 ms 616 KB Output is correct
3 Correct 1099 ms 488 KB Output is correct
4 Correct 783 ms 492 KB Output is correct
5 Correct 799 ms 400 KB Output is correct
6 Correct 634 ms 616 KB Output is correct
7 Correct 546 ms 528 KB Output is correct
8 Correct 4 ms 468 KB Output is correct
9 Correct 6 ms 476 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 743 ms 480 KB Output is correct
12 Correct 572 ms 728 KB Output is correct
13 Correct 500 ms 528 KB Output is correct
14 Correct 539 ms 488 KB Output is correct
15 Correct 64 ms 420 KB Output is correct
16 Correct 101 ms 552 KB Output is correct
17 Correct 112 ms 592 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1087 ms 468 KB Output is correct
2 Correct 746 ms 468 KB Output is correct
3 Correct 775 ms 400 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 4 ms 468 KB Output is correct
6 Correct 2 ms 472 KB Output is correct
7 Correct 707 ms 488 KB Output is correct
8 Correct 1224 ms 400 KB Output is correct
9 Correct 877 ms 400 KB Output is correct
10 Correct 736 ms 400 KB Output is correct
11 Correct 8 ms 472 KB Output is correct
12 Correct 5 ms 588 KB Output is correct
13 Correct 5 ms 468 KB Output is correct
14 Correct 4 ms 428 KB Output is correct
15 Correct 3 ms 432 KB Output is correct
16 Correct 680 ms 488 KB Output is correct
17 Correct 559 ms 484 KB Output is correct
18 Correct 624 ms 400 KB Output is correct
19 Correct 560 ms 400 KB Output is correct
20 Correct 665 ms 400 KB Output is correct

Subtask #5
50.0 / 61.0

# Verdict Execution time Memory Grader output
1 Partially correct 698 ms 656 KB Partially correct
2 Partially correct 432 ms 636 KB Partially correct
3 Correct 960 ms 400 KB Output is correct
4 Correct 619 ms 400 KB Output is correct
5 Correct 624 ms 620 KB Output is correct
6 Partially correct 575 ms 652 KB Partially correct
7 Partially correct 470 ms 540 KB Partially correct
8 Correct 4 ms 468 KB Output is correct
9 Correct 6 ms 472 KB Output is correct
10 Correct 3 ms 468 KB Output is correct
11 Partially correct 568 ms 524 KB Partially correct
12 Partially correct 570 ms 528 KB Partially correct
13 Correct 907 ms 400 KB Output is correct
14 Correct 722 ms 400 KB Output is correct
15 Correct 763 ms 400 KB Output is correct
16 Partially correct 501 ms 528 KB Partially correct
17 Correct 714 ms 400 KB Output is correct
18 Partially correct 585 ms 712 KB Partially correct
19 Partially correct 523 ms 768 KB Partially correct
20 Partially correct 669 ms 484 KB Partially correct
21 Correct 70 ms 412 KB Output is correct
22 Partially correct 107 ms 528 KB Partially correct
23 Partially correct 140 ms 552 KB Partially correct
24 Correct 6 ms 472 KB Output is correct
25 Correct 7 ms 476 KB Output is correct
26 Correct 5 ms 460 KB Output is correct
27 Correct 4 ms 468 KB Output is correct
28 Correct 2 ms 468 KB Output is correct
29 Correct 613 ms 400 KB Output is correct
30 Correct 487 ms 400 KB Output is correct
31 Correct 634 ms 488 KB Output is correct
32 Correct 556 ms 492 KB Output is correct
33 Correct 457 ms 400 KB Output is correct
34 Partially correct 452 ms 644 KB Partially correct
35 Partially correct 482 ms 600 KB Partially correct
36 Partially correct 545 ms 720 KB Partially correct
37 Partially correct 577 ms 732 KB Partially correct
38 Partially correct 640 ms 724 KB Partially correct
39 Partially correct 511 ms 740 KB Partially correct
40 Partially correct 500 ms 776 KB Partially correct
41 Partially correct 501 ms 808 KB Partially correct
42 Partially correct 61 ms 528 KB Partially correct
43 Partially correct 102 ms 528 KB Partially correct
44 Partially correct 127 ms 528 KB Partially correct
45 Partially correct 181 ms 528 KB Partially correct
46 Partially correct 398 ms 532 KB Partially correct
47 Partially correct 411 ms 528 KB Partially correct
48 Partially correct 88 ms 656 KB Partially correct
49 Partially correct 66 ms 720 KB Partially correct