oj.uz

Submission #413264

# Submission time Handle Problem Language Result Execution time Memory
413264 2021-05-28T12:08:36 Z SuhaibSawalha1 Stations (IOI20_stations) C++17
13 / 100
 1174 ms 656 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()) {
		iota(lab.begin(), lab.end(), 0);
		return lab;
	}
	if (all_of(adj.begin(), adj.end(), [](auto &e) {return e.size() < 3;})) {
		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 629 ms 520 KB Output is correct
2 Correct 490 ms 648 KB Output is correct
3 Correct 1174 ms 400 KB Output is correct
4 Correct 723 ms 488 KB Output is correct
5 Correct 664 ms 400 KB Output is correct
6 Correct 681 ms 528 KB Output is correct
7 Correct 616 ms 484 KB Output is correct
8 Correct 5 ms 452 KB Output is correct
9 Correct 6 ms 460 KB Output is correct
10 Correct 4 ms 468 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 704 ms 576 KB Output is correct
2 Correct 812 ms 588 KB Output is correct
3 Correct 1097 ms 400 KB Output is correct
4 Correct 834 ms 400 KB Output is correct
5 Correct 693 ms 400 KB Output is correct
6 Correct 657 ms 488 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 616 ms 612 KB Output is correct
2 Correct 513 ms 620 KB Output is correct
3 Correct 1001 ms 400 KB Output is correct
4 Correct 782 ms 472 KB Output is correct
5 Correct 644 ms 488 KB Output is correct
6 Correct 518 ms 548 KB Output is correct
7 Correct 546 ms 656 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 7 ms 472 KB Output is correct
10 Correct 3 ms 476 KB Output is correct
11 Incorrect 813 ms 400 KB Wrong query response.
12 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1044 ms 400 KB Output is correct
2 Correct 720 ms 400 KB Output is correct
3 Correct 767 ms 400 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 6 ms 556 KB Output is correct
6 Correct 2 ms 452 KB Output is correct
7 Incorrect 635 ms 532 KB Wrong query response.
8 Halted 0 ms 0 KB -

Subtask #5
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 658 ms 600 KB Output is correct
2 Correct 519 ms 528 KB Output is correct
3 Correct 998 ms 400 KB Output is correct
4 Correct 787 ms 400 KB Output is correct
5 Correct 807 ms 400 KB Output is correct
6 Correct 627 ms 612 KB Output is correct
7 Correct 610 ms 480 KB Output is correct
8 Correct 3 ms 476 KB Output is correct
9 Correct 4 ms 468 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 520 ms 528 KB Output is correct
12 Correct 699 ms 528 KB Output is correct
13 Correct 946 ms 564 KB Output is correct
14 Correct 755 ms 400 KB Output is correct
15 Correct 666 ms 400 KB Output is correct
16 Correct 472 ms 528 KB Output is correct
17 Incorrect 678 ms 400 KB Wrong query response.
18 Halted 0 ms 0 KB -