oj.uz

Submission #413287

# Submission time Handle Problem Language Result Execution time Memory
413287 2021-05-28T12:42:27 Z SuhaibSawalha1 Stations (IOI20_stations) C++17
13 / 100
 1166 ms 736 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++;
}

void dfs2 (int u, int p, int lb) {
	lab[u] = lb;
	for (int v : adj[u]) {
		if (v ^ p) {
			dfs2(v, u, lb + 1);
		}
	}
}

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;
	}
	array<int, 2> p {0};
	for (int i = 0; i < n; ++i) {
		p = max(p, {(int)adj[i].size(), i});
	}
	int lb = 1e4;
	lab[p[1]] = lb;
	for (int v : adj[p[1]]) {
		lb += 1e4;
		dfs2(v, p[1], lb);
	}
	return lab;
}
 
int find_next_station(int s, int t, vector<int> c) {
	if (c.size() == 1) {
		return c[0];
	}
	int o = 1e4;
	if (s >= o) {
		if (s / o == t / o) {
			return s - (t < s) + (t > s);
		}
		return s == o ? t / o * o : s % o ? s - 1 : o;	
	}
	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 561 ms 528 KB Output is correct
2 Correct 514 ms 528 KB Output is correct
3 Correct 978 ms 400 KB Output is correct
4 Correct 802 ms 484 KB Output is correct
5 Correct 599 ms 488 KB Output is correct
6 Correct 547 ms 612 KB Output is correct
7 Correct 599 ms 528 KB Output is correct
8 Correct 4 ms 468 KB Output is correct
9 Correct 6 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 464 ms 552 KB Output is correct
2 Correct 693 ms 528 KB Output is correct
3 Correct 1071 ms 528 KB Output is correct
4 Correct 826 ms 528 KB Output is correct
5 Correct 703 ms 400 KB Output is correct
6 Correct 485 ms 528 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 735 ms 656 KB Output is correct
2 Correct 601 ms 736 KB Output is correct
3 Correct 1047 ms 400 KB Output is correct
4 Correct 745 ms 400 KB Output is correct
5 Correct 657 ms 400 KB Output is correct
6 Correct 530 ms 488 KB Output is correct
7 Correct 565 ms 528 KB Output is correct
8 Correct 4 ms 468 KB Output is correct
9 Correct 5 ms 468 KB Output is correct
10 Correct 2 ms 476 KB Output is correct
11 Correct 788 ms 488 KB Output is correct
12 Incorrect 5 ms 328 KB Invalid labels (values out of range). scenario=0, k=1000000, vertex=0, label=1360057
13 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1067 ms 400 KB Output is correct
2 Correct 872 ms 400 KB Output is correct
3 Correct 761 ms 400 KB Output is correct
4 Correct 3 ms 480 KB Output is correct
5 Correct 6 ms 476 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 702 ms 400 KB Output is correct
8 Correct 963 ms 476 KB Output is correct
9 Correct 846 ms 480 KB Output is correct
10 Correct 622 ms 400 KB Output is correct
11 Incorrect 1 ms 200 KB Invalid labels (duplicates values). scenario=5, label=20001
12 Halted 0 ms 0 KB -

Subtask #5
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 609 ms 596 KB Output is correct
2 Correct 501 ms 600 KB Output is correct
3 Correct 1166 ms 400 KB Output is correct
4 Correct 689 ms 488 KB Output is correct
5 Correct 738 ms 456 KB Output is correct
6 Correct 612 ms 528 KB Output is correct
7 Correct 463 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 2 ms 460 KB Output is correct
11 Correct 514 ms 624 KB Output is correct
12 Correct 619 ms 488 KB Output is correct
13 Correct 1063 ms 400 KB Output is correct
14 Correct 742 ms 488 KB Output is correct
15 Correct 686 ms 400 KB Output is correct
16 Correct 635 ms 528 KB Output is correct
17 Partially correct 706 ms 528 KB Partially correct
18 Partially correct 477 ms 656 KB Partially correct
19 Partially correct 486 ms 604 KB Partially correct
20 Partially correct 599 ms 556 KB Partially correct
21 Partially correct 87 ms 400 KB Partially correct
22 Partially correct 71 ms 552 KB Partially correct
23 Partially correct 121 ms 640 KB Partially correct
24 Incorrect 1 ms 200 KB Invalid labels (duplicates values). scenario=5, label=40001
25 Halted 0 ms 0 KB -