oj.uz

Submission #413533

# Submission time Handle Problem Language Result Execution time Memory
413533 2021-05-28T20:52:57 Z SuhaibSawalha1 Stations (IOI20_stations) C++17
29 / 100
 1115 ms 656 KB 
#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
 
vector<vector<int>> adj;
vector<int> lab;
int cnt, inc = 7;
 
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);
		}
	}
}

void dfs3 (int u = 0, int p = -1, int lb = 0) {
	lab[u] = lb += pow(10, inc--);
	for (int v : adj[u]) {
		if (v ^ p) {
			dfs3(v, u, lb);
		}
	}
}
 
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;
	}
	if (k == 1e6) {
		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;
	}
	dfs3();
	return lab;
}

vector<int> go (int v) {
	string s = to_string(v);
	vector<int> a;
	for (int i = 7; ~i; --i) {
		if (s[7 - i] == '1') {
			a.push_back(pow(10, i));
		}
	}
	return a;
}

int first (vector<int> &a, vector<int> &b) {
	for (int i = 0; i < (int)min(a.size(), b.size()); ++i) {
		if (a[i] != b[i]) {
			return 0;
		}
	}
	if (a.size() < b.size()) {
		return b[a.size()];
	}
	return 0;
}
 
int find_next_station(int s, int t, vector<int> c) {
	if (c.size() == 1) {
		return c[0];
	}
	int o = 1e7;
	if (s >= o) {
		vector<int> a = go(s), b = go(t);
		if (int v = first(a, b)) {
			return s + v;
		}
		return s - a.back();
	}
	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 589 ms 640 KB Output is correct
2 Correct 537 ms 612 KB Output is correct
3 Correct 869 ms 400 KB Output is correct
4 Correct 865 ms 488 KB Output is correct
5 Correct 553 ms 492 KB Output is correct
6 Correct 462 ms 484 KB Output is correct
7 Correct 530 ms 528 KB Output is correct
8 Correct 3 ms 480 KB Output is correct
9 Correct 6 ms 468 KB Output is correct
10 Correct 2 ms 544 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 606 ms 528 KB Output is correct
2 Correct 678 ms 544 KB Output is correct
3 Correct 1113 ms 488 KB Output is correct
4 Correct 869 ms 400 KB Output is correct
5 Correct 609 ms 492 KB Output is correct
6 Correct 543 ms 488 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 706 ms 656 KB Output is correct
2 Correct 554 ms 616 KB Output is correct
3 Correct 1115 ms 400 KB Output is correct
4 Correct 729 ms 492 KB Output is correct
5 Correct 755 ms 512 KB Output is correct
6 Correct 546 ms 484 KB Output is correct
7 Correct 562 ms 520 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 4 ms 468 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 764 ms 400 KB Output is correct
12 Correct 605 ms 612 KB Output is correct
13 Correct 538 ms 612 KB Output is correct
14 Correct 412 ms 476 KB Output is correct
15 Correct 66 ms 468 KB Output is correct
16 Correct 83 ms 592 KB Output is correct
17 Correct 138 ms 556 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 921 ms 400 KB Output is correct
2 Correct 720 ms 400 KB Output is correct
3 Correct 674 ms 400 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 4 ms 468 KB Output is correct
6 Correct 3 ms 464 KB Output is correct
7 Incorrect 1 ms 284 KB Invalid labels (duplicates values). scenario=3, label=0
8 Halted 0 ms 0 KB -

Subtask #5
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 656 ms 632 KB Output is correct
2 Correct 529 ms 528 KB Output is correct
3 Correct 889 ms 432 KB Output is correct
4 Correct 801 ms 472 KB Output is correct
5 Correct 660 ms 400 KB Output is correct
6 Correct 583 ms 608 KB Output is correct
7 Correct 587 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 476 KB Output is correct
11 Correct 611 ms 612 KB Output is correct
12 Correct 612 ms 488 KB Output is correct
13 Correct 989 ms 464 KB Output is correct
14 Correct 839 ms 400 KB Output is correct
15 Correct 744 ms 400 KB Output is correct
16 Correct 516 ms 528 KB Output is correct
17 Incorrect 1 ms 200 KB Invalid labels (duplicates values). scenario=4, label=0
18 Halted 0 ms 0 KB -