oj.uz

Submission #430369

# Submission time Handle Problem Language Result Execution time Memory
430369 2021-06-16T13:11:24 Z Keshi Stations (IOI20_stations) C++17
100 / 100
 1168 ms 980 KB 
//In the name of God
#include<bits/stdc++.h>
#include "stations.h"
using namespace std;

typedef int ll;
typedef pair<ll, ll> pll;

const ll maxn = 1100;
const ll mod = 1e9 + 7;
const ll inf = 1e9;

#define Mp make_pair
#define F first
#define S second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define Sz(x) ll((x).size())

ll t, st[maxn], ft[maxn], h[maxn];
vector<ll> g[maxn];

void dfs(ll v, ll p){
	st[v] = t++;
	for(ll u : g[v]){
		if(u != p){
			h[u] = h[v] + 1;
			dfs(u, v);
		}
	}
	ft[v] = t++;
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	for(ll i = 0; i < n; i++){
		g[i].clear();
	}
	vector<int> labels(n), sonic(n);
	for(ll i = 0; i < n - 1; i++){
		g[u[i]].pb(v[i]);
		g[v[i]].pb(u[i]);
	}
	dfs(0, 0);
	for (int i = 0; i < n; i++) {
		if(h[i] & 1) labels[i] = ft[i];
		else labels[i] = st[i];
		sonic[i] = labels[i];
	}
	sort(all(sonic));
	for(ll i = 0; i < n; i++){
		labels[i] = (lower_bound(all(sonic), labels[i]) - sonic.begin());
	}
	return labels;
}

int find_next_station(int s, int t, vector<int> c){
	if(Sz(c) == 1) return c[0];
	sort(all(c));
	if(s < c[0]){
		ll ls = s + 1;
		for(ll i = 0; i < Sz(c) - 1; i++){
			if(ls <= t && t <= c[i]) return c[i];
			ls = c[i] + 1;
		}
		return c.back();
	}
	ll ls = s - 1;
	for(ll i = Sz(c) - 1; i > 0; i--){
		if(c[i] <= t && t <= ls) return c[i];
		ls = c[i] - 1;
	}
	return c[0];
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 796 ms 696 KB Output is correct
2 Correct 559 ms 528 KB Output is correct
3 Correct 1069 ms 500 KB Output is correct
4 Correct 707 ms 508 KB Output is correct
5 Correct 631 ms 456 KB Output is correct
6 Correct 578 ms 520 KB Output is correct
7 Correct 551 ms 508 KB Output is correct
8 Correct 3 ms 716 KB Output is correct
9 Correct 4 ms 596 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 518 ms 512 KB Output is correct
2 Correct 546 ms 540 KB Output is correct
3 Correct 1061 ms 564 KB Output is correct
4 Correct 738 ms 528 KB Output is correct
5 Correct 677 ms 580 KB Output is correct
6 Correct 432 ms 528 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 547 ms 732 KB Output is correct
2 Correct 537 ms 980 KB Output is correct
3 Correct 1168 ms 528 KB Output is correct
4 Correct 873 ms 528 KB Output is correct
5 Correct 758 ms 504 KB Output is correct
6 Correct 704 ms 620 KB Output is correct
7 Correct 704 ms 492 KB Output is correct
8 Correct 3 ms 448 KB Output is correct
9 Correct 7 ms 468 KB Output is correct
10 Correct 2 ms 448 KB Output is correct
11 Correct 660 ms 400 KB Output is correct
12 Correct 641 ms 748 KB Output is correct
13 Correct 715 ms 608 KB Output is correct
14 Correct 593 ms 492 KB Output is correct
15 Correct 91 ms 552 KB Output is correct
16 Correct 92 ms 532 KB Output is correct
17 Correct 121 ms 576 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1023 ms 656 KB Output is correct
2 Correct 732 ms 512 KB Output is correct
3 Correct 724 ms 528 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 6 ms 604 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 681 ms 528 KB Output is correct
8 Correct 1117 ms 632 KB Output is correct
9 Correct 839 ms 516 KB Output is correct
10 Correct 700 ms 528 KB Output is correct
11 Correct 7 ms 596 KB Output is correct
12 Correct 6 ms 596 KB Output is correct
13 Correct 6 ms 596 KB Output is correct
14 Correct 3 ms 596 KB Output is correct
15 Correct 2 ms 464 KB Output is correct
16 Correct 548 ms 528 KB Output is correct
17 Correct 607 ms 528 KB Output is correct
18 Correct 648 ms 516 KB Output is correct
19 Correct 641 ms 528 KB Output is correct
20 Correct 698 ms 512 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 655 ms 712 KB Output is correct
2 Correct 558 ms 528 KB Output is correct
3 Correct 1001 ms 492 KB Output is correct
4 Correct 710 ms 400 KB Output is correct
5 Correct 736 ms 528 KB Output is correct
6 Correct 548 ms 528 KB Output is correct
7 Correct 497 ms 528 KB Output is correct
8 Correct 3 ms 472 KB Output is correct
9 Correct 4 ms 596 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 549 ms 500 KB Output is correct
12 Correct 574 ms 528 KB Output is correct
13 Correct 960 ms 512 KB Output is correct
14 Correct 934 ms 528 KB Output is correct
15 Correct 699 ms 528 KB Output is correct
16 Correct 492 ms 512 KB Output is correct
17 Correct 736 ms 516 KB Output is correct
18 Correct 576 ms 660 KB Output is correct
19 Correct 699 ms 752 KB Output is correct
20 Correct 509 ms 512 KB Output is correct
21 Correct 62 ms 528 KB Output is correct
22 Correct 106 ms 528 KB Output is correct
23 Correct 117 ms 656 KB Output is correct
24 Correct 4 ms 468 KB Output is correct
25 Correct 7 ms 596 KB Output is correct
26 Correct 5 ms 604 KB Output is correct
27 Correct 5 ms 548 KB Output is correct
28 Correct 2 ms 596 KB Output is correct
29 Correct 661 ms 528 KB Output is correct
30 Correct 774 ms 528 KB Output is correct
31 Correct 736 ms 556 KB Output is correct
32 Correct 637 ms 400 KB Output is correct
33 Correct 694 ms 540 KB Output is correct
34 Correct 309 ms 640 KB Output is correct
35 Correct 580 ms 660 KB Output is correct
36 Correct 534 ms 760 KB Output is correct
37 Correct 571 ms 648 KB Output is correct
38 Correct 587 ms 624 KB Output is correct
39 Correct 460 ms 612 KB Output is correct
40 Correct 589 ms 884 KB Output is correct
41 Correct 471 ms 740 KB Output is correct
42 Correct 68 ms 528 KB Output is correct
43 Correct 131 ms 656 KB Output is correct
44 Correct 157 ms 528 KB Output is correct
45 Correct 210 ms 672 KB Output is correct
46 Correct 448 ms 572 KB Output is correct
47 Correct 430 ms 668 KB Output is correct
48 Correct 87 ms 676 KB Output is correct
49 Correct 60 ms 904 KB Output is correct