oj.uz

Submission #396083

# Submission time Handle Problem Language Result Execution time Memory
396083 2021-04-29T12:30:44 Z InternetPerson10 Stations (IOI20_stations) C++17
100 / 100
 1164 ms 820 KB 
#include "stations.h"
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> adj;
vector<int> sub;
vector<int> labels;

int sub_calc(int v, int par) {
	int ans = 1;
	for(int i = 0; i < (int)adj[v].size(); i++) {
		if(adj[v][i] == par) continue;
		ans += sub_calc(adj[v][i], v);
	}
	// cout << v << ' ' << ans << '\n';
	sub[v] = ans;
	return sub[v];
}

void rec(int v, int l, int u, int par, int d) { // even: min, odd: max
	if(d%2) { 
		labels[v] = u-1;
		u--;
	}
	else {
		labels[v] = l;
		l++;
	}
	for(int i = 0; i < (int)adj[v].size(); i++) {
		if(adj[v][i] == par) continue;
		rec(adj[v][i], l, l + sub[adj[v][i]], v, d+1);
		l += sub[adj[v][i]];
	}
	// cout << v << ' ' << labels[v] << '\n';
	return;
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	vector<vector<int>>().swap(adj);
	vector<int>().swap(sub);
	vector<int>().swap(labels);
	for(int i = 0; i < n; i++) {
		adj.push_back(vector<int>());
		sub.push_back(0);
		labels.push_back(0);
	}
	for(int i = 0; i < n-1; i++) {
		int x = u[i];
		int y = v[i];
		adj[x].push_back(y);
		adj[y].push_back(x);
	}
	sub_calc(0, -1);
	rec(0, 0, n, -1, 0);
	return labels;
}

int find_next_station(int s, int t, vector<int> c) {
	if(s < c[0]) {
		sort(c.begin(), c.end());
		if(t < s) return c[c.size() - 1];
		for(int i = 0; i < (int)c.size(); i++) {
			if(t <= c[i]) return c[i];
		}
		return c[c.size()-1];
	}
	else {
		sort(c.rbegin(), c.rend());
		if(t >= s) return c[c.size() - 1];
		for(int i = 0; i < (int)c.size(); i++) {
			if(t >= c[i]) return c[i];
		}
		return c[c.size()-1];
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 640 ms 620 KB Output is correct
2 Correct 534 ms 656 KB Output is correct
3 Correct 1162 ms 452 KB Output is correct
4 Correct 676 ms 496 KB Output is correct
5 Correct 828 ms 400 KB Output is correct
6 Correct 467 ms 624 KB Output is correct
7 Correct 546 ms 620 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 3 ms 480 KB Output is correct
10 Correct 2 ms 724 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 541 ms 520 KB Output is correct
2 Correct 667 ms 588 KB Output is correct
3 Correct 1164 ms 404 KB Output is correct
4 Correct 802 ms 400 KB Output is correct
5 Correct 680 ms 492 KB Output is correct
6 Correct 602 ms 528 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 552 ms 656 KB Output is correct
2 Correct 587 ms 656 KB Output is correct
3 Correct 1017 ms 400 KB Output is correct
4 Correct 864 ms 512 KB Output is correct
5 Correct 622 ms 400 KB Output is correct
6 Correct 453 ms 656 KB Output is correct
7 Correct 525 ms 620 KB Output is correct
8 Correct 3 ms 472 KB Output is correct
9 Correct 5 ms 472 KB Output is correct
10 Correct 2 ms 472 KB Output is correct
11 Correct 531 ms 400 KB Output is correct
12 Correct 497 ms 652 KB Output is correct
13 Correct 558 ms 736 KB Output is correct
14 Correct 507 ms 528 KB Output is correct
15 Correct 68 ms 476 KB Output is correct
16 Correct 85 ms 632 KB Output is correct
17 Correct 138 ms 548 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 934 ms 404 KB Output is correct
2 Correct 790 ms 400 KB Output is correct
3 Correct 712 ms 492 KB Output is correct
4 Correct 2 ms 472 KB Output is correct
5 Correct 4 ms 476 KB Output is correct
6 Correct 2 ms 472 KB Output is correct
7 Correct 740 ms 564 KB Output is correct
8 Correct 1045 ms 528 KB Output is correct
9 Correct 703 ms 400 KB Output is correct
10 Correct 539 ms 492 KB Output is correct
11 Correct 6 ms 472 KB Output is correct
12 Correct 5 ms 472 KB Output is correct
13 Correct 5 ms 472 KB Output is correct
14 Correct 5 ms 472 KB Output is correct
15 Correct 2 ms 472 KB Output is correct
16 Correct 601 ms 420 KB Output is correct
17 Correct 587 ms 532 KB Output is correct
18 Correct 597 ms 492 KB Output is correct
19 Correct 618 ms 400 KB Output is correct
20 Correct 579 ms 400 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 583 ms 620 KB Output is correct
2 Correct 575 ms 656 KB Output is correct
3 Correct 949 ms 400 KB Output is correct
4 Correct 795 ms 400 KB Output is correct
5 Correct 709 ms 492 KB Output is correct
6 Correct 512 ms 656 KB Output is correct
7 Correct 551 ms 600 KB Output is correct
8 Correct 3 ms 472 KB Output is correct
9 Correct 6 ms 472 KB Output is correct
10 Correct 2 ms 472 KB Output is correct
11 Correct 547 ms 488 KB Output is correct
12 Correct 527 ms 648 KB Output is correct
13 Correct 1001 ms 400 KB Output is correct
14 Correct 643 ms 400 KB Output is correct
15 Correct 712 ms 520 KB Output is correct
16 Correct 588 ms 508 KB Output is correct
17 Correct 651 ms 496 KB Output is correct
18 Correct 575 ms 688 KB Output is correct
19 Correct 583 ms 692 KB Output is correct
20 Correct 484 ms 484 KB Output is correct
21 Correct 75 ms 508 KB Output is correct
22 Correct 95 ms 528 KB Output is correct
23 Correct 93 ms 528 KB Output is correct
24 Correct 7 ms 472 KB Output is correct
25 Correct 8 ms 472 KB Output is correct
26 Correct 6 ms 472 KB Output is correct
27 Correct 5 ms 476 KB Output is correct
28 Correct 2 ms 472 KB Output is correct
29 Correct 647 ms 496 KB Output is correct
30 Correct 654 ms 488 KB Output is correct
31 Correct 620 ms 400 KB Output is correct
32 Correct 722 ms 488 KB Output is correct
33 Correct 537 ms 492 KB Output is correct
34 Correct 315 ms 656 KB Output is correct
35 Correct 468 ms 620 KB Output is correct
36 Correct 587 ms 820 KB Output is correct
37 Correct 549 ms 528 KB Output is correct
38 Correct 650 ms 648 KB Output is correct
39 Correct 581 ms 704 KB Output is correct
40 Correct 617 ms 604 KB Output is correct
41 Correct 488 ms 652 KB Output is correct
42 Correct 76 ms 592 KB Output is correct
43 Correct 127 ms 600 KB Output is correct
44 Correct 138 ms 600 KB Output is correct
45 Correct 231 ms 548 KB Output is correct
46 Correct 337 ms 484 KB Output is correct
47 Correct 338 ms 604 KB Output is correct
48 Correct 81 ms 600 KB Output is correct
49 Correct 77 ms 656 KB Output is correct