oj.uz

Submission #413288

# Submission time Handle Problem Language Result Execution time Memory
413288 2021-05-28T12:46:33 Z SuhaibSawalha1 Stations (IOI20_stations) C++17
29 / 100
 1203 ms 708 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 = 1e3;
	lab[p[1]] = lb;
	for (int v : adj[p[1]]) {
		lb += 1e3;
		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 = 1e3;
	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 720 ms 528 KB Output is correct
2 Correct 600 ms 612 KB Output is correct
3 Correct 1203 ms 400 KB Output is correct
4 Correct 1012 ms 484 KB Output is correct
5 Correct 680 ms 528 KB Output is correct
6 Correct 543 ms 616 KB Output is correct
7 Correct 538 ms 528 KB Output is correct
8 Correct 5 ms 468 KB Output is correct
9 Correct 4 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 603 ms 596 KB Output is correct
2 Correct 728 ms 528 KB Output is correct
3 Correct 1045 ms 404 KB Output is correct
4 Correct 691 ms 484 KB Output is correct
5 Correct 671 ms 488 KB Output is correct
6 Correct 666 ms 488 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 617 ms 620 KB Output is correct
2 Correct 559 ms 656 KB Output is correct
3 Correct 909 ms 400 KB Output is correct
4 Correct 665 ms 480 KB Output is correct
5 Correct 720 ms 520 KB Output is correct
6 Correct 560 ms 480 KB Output is correct
7 Correct 496 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 3 ms 468 KB Output is correct
11 Correct 545 ms 400 KB Output is correct
12 Correct 618 ms 708 KB Output is correct
13 Correct 558 ms 696 KB Output is correct
14 Correct 531 ms 488 KB Output is correct
15 Correct 65 ms 400 KB Output is correct
16 Correct 94 ms 528 KB Output is correct
17 Correct 120 ms 528 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 948 ms 480 KB Output is correct
2 Correct 723 ms 492 KB Output is correct
3 Correct 794 ms 484 KB Output is correct
4 Correct 5 ms 468 KB Output is correct
5 Correct 6 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 732 ms 424 KB Output is correct
8 Correct 1140 ms 484 KB Output is correct
9 Correct 808 ms 400 KB Output is correct
10 Correct 639 ms 488 KB Output is correct
11 Incorrect 1 ms 200 KB Invalid labels (duplicates values). scenario=5, label=2001
12 Halted 0 ms 0 KB -

Subtask #5
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 643 ms 664 KB Output is correct
2 Correct 518 ms 620 KB Output is correct
3 Correct 984 ms 400 KB Output is correct
4 Correct 775 ms 488 KB Output is correct
5 Correct 708 ms 400 KB Output is correct
6 Correct 504 ms 656 KB Output is correct
7 Correct 497 ms 612 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
11 Correct 454 ms 480 KB Output is correct
12 Correct 641 ms 488 KB Output is correct
13 Correct 961 ms 524 KB Output is correct
14 Correct 715 ms 400 KB Output is correct
15 Correct 701 ms 400 KB Output is correct
16 Correct 528 ms 488 KB Output is correct
17 Partially correct 640 ms 400 KB Partially correct
18 Partially correct 617 ms 640 KB Partially correct
19 Partially correct 546 ms 648 KB Partially correct
20 Partially correct 447 ms 488 KB Partially correct
21 Partially correct 67 ms 404 KB Partially correct
22 Partially correct 93 ms 528 KB Partially correct
23 Partially correct 128 ms 540 KB Partially correct
24 Incorrect 1 ms 200 KB Invalid labels (duplicates values). scenario=5, label=4001
25 Halted 0 ms 0 KB -