oj.uz

Submission #362024

# Submission time Handle Problem Language Result Execution time Memory
362024 2021-02-01T14:57:56 Z valerikk Stations (IOI20_stations) C++17
52.3205 / 100
 1085 ms 1372 KB 
#include <bits/stdc++.h>

using namespace std; 

const int N = 1000;

vector<int> g[N];
int T = 0;
vector<int> l;

int dfs(int v, int p = -1) {
    l[v] = T++;
    int mx = l[v];
    for (int u : g[v]) {
        if (u != p) mx = max(mx, dfs(u, v));
    }
    l[v] *= N;
    l[v] += mx;
    return mx;
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
    for (int i = 0; i < n; i++) g[i].clear();
    for (int i = 0; i < n - 1; i++) {
        g[u[i]].push_back(v[i]);
        g[v[i]].push_back(u[i]);
    }
    l.resize(n);
    T = 0;
    dfs(0);
    //for (int &i : l) assert(i >= 0 && i <= k);
    return l;
}

int find_next_station(int s, int t, vector<int> c) {
    int p;
    for (int v : c) {
        if (v / N <= s / N && s / N <= v % N) p = v; else {
            if (v / N <= t / N && t / N <= v % N) return v;
        } 
    }
    return p;
}

#ifdef LOCAL
static int max_label = 0;
static int r, n, k, q;
static std::vector<int> u, v, labels, answers;
static std::map<int, int> reverse_labels;
static std::vector<std::vector<int>> adjlist;
static int s, t, w;
static std::vector<int> c;

int main() {
	assert(scanf("%d", &r) == 1);
	for (int tc = 0; tc < r; tc++) {
		assert(scanf("%d%d", &n, &k) == 2);
		u.resize(n - 1);
		v.resize(n - 1);
		adjlist.clear();
		adjlist.resize(n);
		for (int i = 0; i < n - 1; i++) {
			assert(scanf("%d%d", &u[i], &v[i]) == 2);
			adjlist[u[i]].push_back(v[i]);
			adjlist[v[i]].push_back(u[i]);
		}
		labels = label(n, k, u, v);
		if ((int)labels.size() != n) {
			printf("Number of labels not equal to %d\n", n);
			exit(0);
		}
		reverse_labels.clear();
		for (int i = 0; i < n; i++) {
			if (labels[i] < 0 || labels[i] > k) {
				printf("Label not in range 0 to %d\n", k);
				exit(0);
			}
			if (reverse_labels.find(labels[i]) != reverse_labels.end()) {
				printf("Labels not unique\n");
				exit(0);
			}
			reverse_labels[labels[i]] = i;
			if (labels[i] > max_label) {
				max_label = labels[i];
			}
		}
		assert(scanf("%d", &q) == 1);
		for (int i = 0; i < q; i++) {
			assert(scanf("%d%d%d", &s, &t, &w) == 3);
			c.clear();
			for (int v : adjlist[s]) {
				c.push_back(labels[v]);
			}
			std::sort(c.begin(), c.end());
			int answer = find_next_station(labels[s], labels[t], c);
			if (!std::binary_search(c.begin(), c.end(), answer)) {
				printf("Label %d returned by find_next_station not found in c\n", answer);
				exit(0);
			}
			answers.push_back(reverse_labels[answer]);
		}
	}
	printf("%d\n", max_label);
	for (int index : answers) {
		printf("%d\n", index);
	}
	exit(0);
}
#endif

Compilation message

stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:36:9: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
   36 |     int p;
      |         ^

Subtask #1
0 / 5.0

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

Subtask #2
0 / 8.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 536 ms 992 KB Output is correct
2 Correct 510 ms 1120 KB Output is correct
3 Correct 1051 ms 984 KB Output is correct
4 Correct 737 ms 952 KB Output is correct
5 Correct 668 ms 1108 KB Output is correct
6 Correct 553 ms 864 KB Output is correct
7 Correct 565 ms 1112 KB Output is correct
8 Correct 3 ms 960 KB Output is correct
9 Correct 5 ms 736 KB Output is correct
10 Correct 2 ms 736 KB Output is correct
11 Correct 695 ms 992 KB Output is correct
12 Correct 567 ms 1216 KB Output is correct
13 Correct 560 ms 896 KB Output is correct
14 Correct 436 ms 908 KB Output is correct
15 Correct 71 ms 944 KB Output is correct
16 Correct 77 ms 736 KB Output is correct
17 Correct 97 ms 736 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1085 ms 864 KB Output is correct
2 Correct 698 ms 952 KB Output is correct
3 Correct 648 ms 736 KB Output is correct
4 Correct 3 ms 952 KB Output is correct
5 Correct 5 ms 952 KB Output is correct
6 Correct 1 ms 864 KB Output is correct
7 Correct 710 ms 736 KB Output is correct
8 Correct 946 ms 1108 KB Output is correct
9 Correct 807 ms 960 KB Output is correct
10 Correct 593 ms 736 KB Output is correct
11 Correct 7 ms 992 KB Output is correct
12 Correct 7 ms 952 KB Output is correct
13 Correct 6 ms 864 KB Output is correct
14 Correct 3 ms 1080 KB Output is correct
15 Correct 2 ms 776 KB Output is correct
16 Correct 550 ms 952 KB Output is correct
17 Correct 622 ms 952 KB Output is correct
18 Correct 518 ms 1164 KB Output is correct
19 Correct 618 ms 864 KB Output is correct
20 Correct 521 ms 952 KB Output is correct

Subtask #5
26.3205 / 61.0

# Verdict Execution time Memory Grader output
1 Partially correct 633 ms 1084 KB Partially correct
2 Partially correct 443 ms 992 KB Partially correct
3 Partially correct 1014 ms 952 KB Partially correct
4 Partially correct 612 ms 736 KB Partially correct
5 Partially correct 572 ms 864 KB Partially correct
6 Partially correct 596 ms 1092 KB Partially correct
7 Partially correct 546 ms 872 KB Partially correct
8 Partially correct 3 ms 904 KB Partially correct
9 Partially correct 5 ms 960 KB Partially correct
10 Partially correct 2 ms 864 KB Partially correct
11 Partially correct 511 ms 864 KB Partially correct
12 Partially correct 569 ms 888 KB Partially correct
13 Partially correct 1018 ms 952 KB Partially correct
14 Partially correct 779 ms 864 KB Partially correct
15 Partially correct 638 ms 1108 KB Partially correct
16 Partially correct 553 ms 864 KB Partially correct
17 Partially correct 723 ms 884 KB Partially correct
18 Partially correct 478 ms 992 KB Partially correct
19 Partially correct 501 ms 992 KB Partially correct
20 Partially correct 478 ms 908 KB Partially correct
21 Partially correct 72 ms 864 KB Partially correct
22 Partially correct 88 ms 908 KB Partially correct
23 Partially correct 113 ms 864 KB Partially correct
24 Partially correct 7 ms 952 KB Partially correct
25 Partially correct 7 ms 952 KB Partially correct
26 Partially correct 6 ms 864 KB Partially correct
27 Partially correct 5 ms 736 KB Partially correct
28 Partially correct 2 ms 1088 KB Partially correct
29 Partially correct 556 ms 736 KB Partially correct
30 Partially correct 564 ms 952 KB Partially correct
31 Partially correct 609 ms 1080 KB Partially correct
32 Partially correct 620 ms 952 KB Partially correct
33 Partially correct 601 ms 864 KB Partially correct
34 Partially correct 366 ms 876 KB Partially correct
35 Partially correct 493 ms 1248 KB Partially correct
36 Partially correct 524 ms 1088 KB Partially correct
37 Partially correct 524 ms 856 KB Partially correct
38 Partially correct 487 ms 968 KB Partially correct
39 Partially correct 513 ms 1236 KB Partially correct
40 Partially correct 546 ms 1064 KB Partially correct
41 Partially correct 588 ms 1372 KB Partially correct
42 Partially correct 74 ms 904 KB Partially correct
43 Partially correct 102 ms 736 KB Partially correct
44 Partially correct 164 ms 736 KB Partially correct
45 Partially correct 217 ms 988 KB Partially correct
46 Partially correct 320 ms 736 KB Partially correct
47 Partially correct 383 ms 736 KB Partially correct
48 Partially correct 67 ms 992 KB Partially correct
49 Partially correct 73 ms 860 KB Partially correct