oj.uz

Submission #413256

# Submission time Handle Problem Language Result Execution time Memory
413256 2021-05-28T11:58:31 Z SuhaibSawalha1 Stations (IOI20_stations) C++17
13 / 100
 1196 ms 744 KB 
#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
 
vector<vector<int>> adj;
vector<int> lab;
int cnt;
 
void dfs (int u, int p = -1) {
	for (int v : adj[u]) {
		if (v ^ p) {
			dfs(v, u);
		}
	}
	lab[u] = cnt++;
}

bool subtask2 () {
	for (int i = 0; i < (int)adj.size(); ++i) {
		vector<int> y{(i - 1) / 2, 2 * i + 1, 2 * i + 2};
		if (!i) {
			y.erase(y.begin());
		}
		sort(adj[i].begin(), adj[i].end());
		while (y.size() > adj[i].size()) {
			y.pop_back();
		}
		if (y != adj[i]) {
			return 0;
		}
	}
	return 1;
}
 
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	adj.assign(n, {});
	lab.resize(n);
	cnt = 0;
	for (int i = 0; i < n - 1; ++i) {
		adj[u[i]].push_back(v[i]);
		adj[v[i]].push_back(u[i]);
	}
	if (!subtask2()) {
		for (int i = 0; i < n; ++i) {
			if (adj[i].size() == 1) {
				dfs(i);
				break;
			}
		}
		return lab;
	}
	iota(lab.begin(), lab.end(), 0);
	return lab;
}
 
int find_next_station(int s, int t, vector<int> c) {
	if (c.size() == 1) {
		return c[0];
	}
	sort(c.begin(), c.end());
	vector<int> y{(s - 1) / 2, 2 * s + 1, 2 * s + 2};
	if (!s) {
		y.erase(y.begin());
	}
	while (y.size() > c.size()) {
		y.pop_back();
	}
	if (y != c) {
		return s - (t < s) + (t > s);
	}
	int e = t;
	while (e) {
		int p = (e - 1) / 2;
		if (p == s) {
			return e;
		}
		e = p;
	}
	return (s - 1) / 2;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 660 ms 616 KB Output is correct
2 Correct 480 ms 744 KB Output is correct
3 Correct 1192 ms 480 KB Output is correct
4 Correct 786 ms 400 KB Output is correct
5 Correct 634 ms 596 KB Output is correct
6 Correct 465 ms 592 KB Output is correct
7 Correct 526 ms 588 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 7 ms 468 KB Output is correct
10 Correct 2 ms 468 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 614 ms 536 KB Output is correct
2 Correct 611 ms 484 KB Output is correct
3 Correct 1033 ms 400 KB Output is correct
4 Correct 735 ms 400 KB Output is correct
5 Correct 783 ms 400 KB Output is correct
6 Correct 462 ms 528 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 523 ms 616 KB Output is correct
2 Correct 499 ms 520 KB Output is correct
3 Correct 934 ms 400 KB Output is correct
4 Correct 691 ms 400 KB Output is correct
5 Correct 670 ms 400 KB Output is correct
6 Correct 591 ms 656 KB Output is correct
7 Correct 486 ms 528 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 5 ms 468 KB Output is correct
10 Correct 3 ms 468 KB Output is correct
11 Incorrect 680 ms 528 KB Wrong query response.
12 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 904 ms 528 KB Output is correct
2 Correct 854 ms 528 KB Output is correct
3 Correct 803 ms 400 KB Output is correct
4 Correct 3 ms 476 KB Output is correct
5 Correct 6 ms 468 KB Output is correct
6 Correct 2 ms 464 KB Output is correct
7 Incorrect 783 ms 464 KB Wrong query response.
8 Halted 0 ms 0 KB -

Subtask #5
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 705 ms 656 KB Output is correct
2 Correct 590 ms 612 KB Output is correct
3 Correct 850 ms 488 KB Output is correct
4 Correct 938 ms 488 KB Output is correct
5 Correct 653 ms 400 KB Output is correct
6 Correct 662 ms 604 KB Output is correct
7 Correct 639 ms 508 KB Output is correct
8 Correct 4 ms 468 KB Output is correct
9 Correct 5 ms 464 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 675 ms 480 KB Output is correct
12 Correct 773 ms 480 KB Output is correct
13 Correct 1196 ms 400 KB Output is correct
14 Correct 750 ms 400 KB Output is correct
15 Correct 674 ms 400 KB Output is correct
16 Correct 505 ms 528 KB Output is correct
17 Incorrect 570 ms 400 KB Wrong query response.
18 Halted 0 ms 0 KB -