oj.uz

Submission #835942

# Submission time Handle Problem Language Result Execution time Memory
835942 2023-08-24T00:00:36 Z JustAmethyst Stations (IOI20_stations) C++17
52.3206 / 100
 815 ms 784 KB 
#include "stations.h"
#include <bits/stdc++.h>
#define sz(x) (int)(x.size())
using namespace std;

const int N = 1000;
vector<int> edges[N];
vector<int> tin(N), tout(N);
int t1, t2;

void dfs(int x, int p) {
	int y;
	tin[x] = t1;
	++t1;

	while (!edges[x].empty()) {
		y = edges[x].back();
		edges[x].pop_back();
		if (y != p) {
			dfs(y, x);
		}
	}
	tout[x] = t2;
	++t2;
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	vector<int> codes(n);
	t1 = 0, t2 = 0;

	for (int i = 0; i < n-1; ++i) {
		edges[u[i]].push_back(v[i]);
		edges[v[i]].push_back(u[i]);
	}

	dfs(0, -1);
	for (int i = 0; i < n; ++i) {
		// cout << sz(edges[i]) << "\n";
		codes[i] = tin[i]*1000 + tout[i];
	}
	return codes;
}

int find_next_station(int s, int e, vector<int> c) {
	int sin = s/1000, sout = s % 1000;
	int ein = e/1000, eout = e % 1000;
	if (ein < sin || eout > sout) {
		for (int x : c) {
			if ((x/1000) <= sin) {
				return x;
			}
		}
	}
	for (int x : c) {
		if ((x/1000) > sin && (x/1000) <= ein && (x%1000) >= eout) {
			return x;
		}
	}

	return -1;
}

// void solve() {
// 	vector<int> labels = label(3, 1000000000, {2, 1}, {0, 0});
// 	for (auto x : labels) {
// 		cout << x << " ";
// 		cout << "\n";
// 	}
// 	cout << "\n";

// 	cout << find_next_station(labels[1], labels[0], {labels[0]}) << "\n";
// 	cout << find_next_station(labels[1], labels[2], {labels[0]}) << "\n";
// 	cout << find_next_station(labels[2], labels[1], {labels[0]}) << "\n";
// 	cout << find_next_station(labels[0], labels[2], {labels[2], labels[1]}) << "\n";
// 	cout << find_next_station(labels[2], labels[0], {labels[0]}) << "\n";
// 	cout << find_next_station(labels[0], labels[1], {labels[2], labels[1]}) << "\n";

// 	// cout << "\n";
// 	// cout << find_next_station(1003, 4001, {2000, 3002, 4}) << "\n";
// }

// int main() {
// 	ios_base::sync_with_stdio(0);
// 	cin.tie(0);
// 	// int t;
// 	// cin >> t;
// 	// while (t--) 
// 	solve();
	
// 	return 0;
// }


// 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);
// }

Subtask #1
0 / 5.0

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

Subtask #2
0 / 8.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 342 ms 652 KB Output is correct
2 Correct 309 ms 676 KB Output is correct
3 Correct 691 ms 420 KB Output is correct
4 Correct 574 ms 416 KB Output is correct
5 Correct 483 ms 544 KB Output is correct
6 Correct 412 ms 548 KB Output is correct
7 Correct 320 ms 548 KB Output is correct
8 Correct 2 ms 740 KB Output is correct
9 Correct 3 ms 628 KB Output is correct
10 Correct 0 ms 748 KB Output is correct
11 Correct 574 ms 416 KB Output is correct
12 Correct 299 ms 692 KB Output is correct
13 Correct 433 ms 656 KB Output is correct
14 Correct 363 ms 544 KB Output is correct
15 Correct 31 ms 748 KB Output is correct
16 Correct 46 ms 728 KB Output is correct
17 Correct 100 ms 728 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 805 ms 416 KB Output is correct
2 Correct 631 ms 416 KB Output is correct
3 Correct 548 ms 676 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 3 ms 500 KB Output is correct
6 Correct 0 ms 492 KB Output is correct
7 Correct 465 ms 544 KB Output is correct
8 Correct 616 ms 416 KB Output is correct
9 Correct 451 ms 420 KB Output is correct
10 Correct 536 ms 728 KB Output is correct
11 Correct 5 ms 620 KB Output is correct
12 Correct 5 ms 628 KB Output is correct
13 Correct 3 ms 500 KB Output is correct
14 Correct 2 ms 620 KB Output is correct
15 Correct 2 ms 620 KB Output is correct
16 Correct 394 ms 420 KB Output is correct
17 Correct 382 ms 548 KB Output is correct
18 Correct 429 ms 416 KB Output is correct
19 Correct 408 ms 420 KB Output is correct
20 Correct 490 ms 612 KB Output is correct

Subtask #5
26.3206 / 61.0

# Verdict Execution time Memory Grader output
1 Partially correct 407 ms 644 KB Partially correct
2 Partially correct 360 ms 728 KB Partially correct
3 Correct 815 ms 420 KB Output is correct
4 Partially correct 526 ms 544 KB Partially correct
5 Partially correct 541 ms 416 KB Partially correct
6 Partially correct 399 ms 548 KB Partially correct
7 Partially correct 428 ms 544 KB Partially correct
8 Partially correct 2 ms 500 KB Partially correct
9 Partially correct 2 ms 624 KB Partially correct
10 Partially correct 0 ms 620 KB Partially correct
11 Partially correct 306 ms 544 KB Partially correct
12 Partially correct 354 ms 544 KB Partially correct
13 Correct 679 ms 544 KB Output is correct
14 Partially correct 468 ms 420 KB Partially correct
15 Partially correct 496 ms 420 KB Partially correct
16 Partially correct 256 ms 672 KB Partially correct
17 Partially correct 497 ms 416 KB Partially correct
18 Partially correct 389 ms 664 KB Partially correct
19 Partially correct 424 ms 652 KB Partially correct
20 Partially correct 371 ms 544 KB Partially correct
21 Partially correct 51 ms 752 KB Partially correct
22 Partially correct 75 ms 728 KB Partially correct
23 Partially correct 74 ms 704 KB Partially correct
24 Partially correct 3 ms 748 KB Partially correct
25 Partially correct 4 ms 500 KB Partially correct
26 Partially correct 4 ms 636 KB Partially correct
27 Partially correct 2 ms 492 KB Partially correct
28 Partially correct 1 ms 504 KB Partially correct
29 Partially correct 359 ms 420 KB Partially correct
30 Partially correct 463 ms 548 KB Partially correct
31 Partially correct 405 ms 420 KB Partially correct
32 Partially correct 361 ms 544 KB Partially correct
33 Partially correct 419 ms 416 KB Partially correct
34 Partially correct 242 ms 548 KB Partially correct
35 Partially correct 315 ms 664 KB Partially correct
36 Partially correct 330 ms 544 KB Partially correct
37 Partially correct 322 ms 784 KB Partially correct
38 Partially correct 307 ms 660 KB Partially correct
39 Partially correct 349 ms 744 KB Partially correct
40 Partially correct 411 ms 664 KB Partially correct
41 Partially correct 258 ms 660 KB Partially correct
42 Partially correct 35 ms 744 KB Partially correct
43 Partially correct 86 ms 700 KB Partially correct
44 Partially correct 117 ms 572 KB Partially correct
45 Partially correct 107 ms 544 KB Partially correct
46 Partially correct 270 ms 548 KB Partially correct
47 Partially correct 208 ms 548 KB Partially correct
48 Partially correct 58 ms 700 KB Partially correct
49 Partially correct 51 ms 684 KB Partially correct