oj.uz

Submission #1052447

# Submission time Handle Problem Language Result Execution time Memory
1052447 2024-08-10T14:39:39 Z dozer Stations (IOI20_stations) C++14
52.3205 / 100
 501 ms 1204 KB 
#include "stations.h"
#include<bits/stdc++.h>
using namespace std;
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define sp " "
#define endl "\n"
#define pii pair<int, int>
#define st first
#define nd second
#define pb push_back
#define ll long long
#define LL node * 2
#define RR node * 2 + 1
#define N 1005

const int modulo = 1e9 + 7;
const ll INF = 2e18 + 7;
const int m = 1000;

int l[N], tin[N], tout[N];
int cntr = 0;
vector<int> adj[N];

void dfs(int node, int root){
	tin[node] = ++cntr;
	for (auto i : adj[node]){
		if (i != root) dfs(i, node);
	}
	tout[node] = cntr;
}


vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	vector<int> labels(n);
	for (int i = 0; i < n; i++)
		adj[i].clear();

	for (int i = 0; i < n - 1; i++){
		adj[u[i]].pb(v[i]);
		adj[v[i]].pb(u[i]);
	}
	cntr = -1;
	int root = 0;
	for (int i = 0; i < n; i++) if (adj[i].size() == 1) root = i;
	dfs(root, -1);

	for (int i = 0; i < n; i++) {
		labels[i] = tin[i] + tout[i] * m;
		//cout<<i<<sp<<tin[i]<<sp<<tout[i]<<sp<<labels[i]<<endl;
	}
	return labels;
}

int find_next_station(int s, int t, vector<int> c) {
	int in = t % m, out = t / m;
	sort(c.begin(), c.end(), [&](int a, int b){
		int ina = a % m, inb = b % m;
		int outa = a / m, outb = b / m;
		if (ina >= inb && outa <= outb) return true;
		if (ina <= inb && outa >= outb) return false;
		return ina < inb;
	});



	for (auto i : c){
		int in2 = i % m, out2 = i / m;
		if (in2 <= in && out2 >= out) return i; 
	}
	return c.back();
	
}
/*


static int max_label = 0;
static int r, n, k, q;
static std::vector<int> u, v, labels, answers;
static std::map<int, int> reverse_labels;
static std::vector<std::vector<int>> adjlist;
static int s, t, w;
static std::vector<int> c;

int main() {
	fileio();
	assert(scanf("%d", &r) == 1);
	for (int tc = 0; tc < r; tc++) {
		assert(scanf("%d%d", &n, &k) == 2);
		u.resize(n - 1);
		v.resize(n - 1);
		adjlist.clear();
		adjlist.resize(n);
		for (int i = 0; i < n - 1; i++) {
			assert(scanf("%d%d", &u[i], &v[i]) == 2);
			adjlist[u[i]].push_back(v[i]);
			adjlist[v[i]].push_back(u[i]);
		}
		labels = label(n, k, u, v);
		if ((int)labels.size() != n) {
			printf("Number of labels not equal to %d\n", n);
			exit(0);
		}
		reverse_labels.clear();
		for (int i = 0; i < n; i++) {
			if (labels[i] < 0 || labels[i] > k) {
				printf("Label not in range 0 to %d\n", k);
				exit(0);
			}
			if (reverse_labels.find(labels[i]) != reverse_labels.end()) {
				printf("Labels not unique\n");
				exit(0);
			}
			reverse_labels[labels[i]] = i;
			if (labels[i] > max_label) {
				max_label = labels[i];
			}
		}
		assert(scanf("%d", &q) == 1);
		for (int i = 0; i < q; i++) {
			assert(scanf("%d%d%d", &s, &t, &w) == 3);
			c.clear();
			for (int v : adjlist[s]) {
				c.push_back(labels[v]);
			}
			std::sort(c.begin(), c.end());
			int answer = find_next_station(labels[s], labels[t], c);
			if (!std::binary_search(c.begin(), c.end(), answer)) {
				printf("Label %d returned by find_next_station not found in c\n", answer);
				exit(0);
			}
			answers.push_back(reverse_labels[answer]);
		}
	}
	printf("%d\n", max_label);
	for (int index : answers) {
		printf("%d\n", index);
	}
	exit(0);
}
*/

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Invalid labels (values out of range). scenario=0, k=1000, vertex=0, label=9001
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 344 KB Invalid labels (values out of range). scenario=0, k=1000, vertex=0, label=520009
2 Halted 0 ms 0 KB -

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 684 KB Output is correct
2 Correct 248 ms 684 KB Output is correct
3 Correct 473 ms 684 KB Output is correct
4 Correct 332 ms 684 KB Output is correct
5 Correct 320 ms 684 KB Output is correct
6 Correct 258 ms 684 KB Output is correct
7 Correct 240 ms 684 KB Output is correct
8 Correct 1 ms 764 KB Output is correct
9 Correct 2 ms 768 KB Output is correct
10 Correct 0 ms 768 KB Output is correct
11 Correct 315 ms 684 KB Output is correct
12 Correct 253 ms 792 KB Output is correct
13 Correct 300 ms 784 KB Output is correct
14 Correct 252 ms 688 KB Output is correct
15 Correct 26 ms 768 KB Output is correct
16 Correct 29 ms 716 KB Output is correct
17 Correct 55 ms 716 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 498 ms 684 KB Output is correct
2 Correct 340 ms 688 KB Output is correct
3 Correct 305 ms 688 KB Output is correct
4 Correct 0 ms 764 KB Output is correct
5 Correct 1 ms 768 KB Output is correct
6 Correct 0 ms 776 KB Output is correct
7 Correct 335 ms 684 KB Output is correct
8 Correct 487 ms 712 KB Output is correct
9 Correct 388 ms 684 KB Output is correct
10 Correct 361 ms 944 KB Output is correct
11 Correct 3 ms 764 KB Output is correct
12 Correct 2 ms 764 KB Output is correct
13 Correct 1 ms 768 KB Output is correct
14 Correct 2 ms 768 KB Output is correct
15 Correct 0 ms 768 KB Output is correct
16 Correct 282 ms 684 KB Output is correct
17 Correct 286 ms 684 KB Output is correct
18 Correct 250 ms 684 KB Output is correct
19 Correct 286 ms 688 KB Output is correct
20 Correct 280 ms 684 KB Output is correct

Subtask #5
26.3205 / 61.0

# Verdict Execution time Memory Grader output
1 Partially correct 323 ms 680 KB Partially correct
2 Partially correct 260 ms 684 KB Partially correct
3 Partially correct 501 ms 688 KB Partially correct
4 Partially correct 363 ms 684 KB Partially correct
5 Partially correct 326 ms 684 KB Partially correct
6 Partially correct 241 ms 684 KB Partially correct
7 Partially correct 218 ms 684 KB Partially correct
8 Partially correct 1 ms 768 KB Partially correct
9 Partially correct 1 ms 768 KB Partially correct
10 Partially correct 0 ms 932 KB Partially correct
11 Partially correct 236 ms 684 KB Partially correct
12 Partially correct 286 ms 684 KB Partially correct
13 Partially correct 500 ms 684 KB Partially correct
14 Partially correct 416 ms 684 KB Partially correct
15 Partially correct 312 ms 684 KB Partially correct
16 Partially correct 254 ms 684 KB Partially correct
17 Partially correct 357 ms 684 KB Partially correct
18 Partially correct 268 ms 932 KB Partially correct
19 Partially correct 268 ms 784 KB Partially correct
20 Partially correct 227 ms 684 KB Partially correct
21 Partially correct 21 ms 780 KB Partially correct
22 Partially correct 32 ms 768 KB Partially correct
23 Partially correct 49 ms 768 KB Partially correct
24 Partially correct 2 ms 776 KB Partially correct
25 Partially correct 3 ms 776 KB Partially correct
26 Partially correct 1 ms 776 KB Partially correct
27 Partially correct 1 ms 776 KB Partially correct
28 Partially correct 0 ms 768 KB Partially correct
29 Partially correct 268 ms 792 KB Partially correct
30 Partially correct 259 ms 684 KB Partially correct
31 Partially correct 267 ms 684 KB Partially correct
32 Partially correct 283 ms 684 KB Partially correct
33 Partially correct 283 ms 684 KB Partially correct
34 Partially correct 169 ms 684 KB Partially correct
35 Partially correct 234 ms 804 KB Partially correct
36 Partially correct 295 ms 780 KB Partially correct
37 Partially correct 218 ms 792 KB Partially correct
38 Partially correct 269 ms 1204 KB Partially correct
39 Partially correct 248 ms 800 KB Partially correct
40 Partially correct 239 ms 812 KB Partially correct
41 Partially correct 261 ms 940 KB Partially correct
42 Partially correct 31 ms 764 KB Partially correct
43 Partially correct 52 ms 716 KB Partially correct
44 Partially correct 69 ms 736 KB Partially correct
45 Partially correct 87 ms 764 KB Partially correct
46 Partially correct 176 ms 684 KB Partially correct
47 Partially correct 174 ms 684 KB Partially correct
48 Partially correct 32 ms 768 KB Partially correct
49 Partially correct 28 ms 764 KB Partially correct