oj.uz

Submission #304990

# Submission time Handle Problem Language Result Execution time Memory
304990 2020-09-22T10:59:45 Z Wu_Ren Stations (IOI20_stations) C++17
100 / 100
 1162 ms 952 KB 
#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
vector<int>ans;
int head[1010],o,cnt;
struct edge{
	int to,link;
}e[2010];
void add_edge(int u,int v){
	e[++o].to=v,e[o].link=head[u],head[u]=o;
	e[++o].to=u,e[o].link=head[v],head[v]=o;
}
void dfs(int u,int pre,int dep){
	if(dep&1) ans[u]=cnt++;
	for(int i=head[u];i;i=e[i].link){
		if(e[i].to==pre) continue;
		dfs(e[i].to,u,dep+1);
	}
	if(!(dep&1)) ans[u]=cnt++;
}
vector<int> label(int n,int k,vector<int>u,vector<int>v){
	for(int i=0;i<n;i++) head[i]=0;
	cnt=o=0,ans.clear(),ans.resize(n);
	for(int i=0;i<n-1;i++) add_edge(u[i],v[i]);
	dfs(0,-1,1);
	return ans;
}

int find_next_station(int s,int t,vector<int>c) {
	if(s<c[0]){
		if(t<s) return c[c.size()-1];
		if(t>=c[c.size()-1]) 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{
		if(t>s) return c[0];
		if(t<c[1]) return c[0];
		for(int i=c.size()-1;i>=0;i--) if(t>=c[i]) return c[i];
		return c[0];
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 805 ms 832 KB Output is correct
2 Correct 583 ms 756 KB Output is correct
3 Correct 1081 ms 752 KB Output is correct
4 Correct 790 ms 640 KB Output is correct
5 Correct 708 ms 640 KB Output is correct
6 Correct 496 ms 896 KB Output is correct
7 Correct 483 ms 780 KB Output is correct
8 Correct 3 ms 776 KB Output is correct
9 Correct 6 ms 768 KB Output is correct
10 Correct 2 ms 640 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 559 ms 776 KB Output is correct
2 Correct 776 ms 796 KB Output is correct
3 Correct 1020 ms 896 KB Output is correct
4 Correct 776 ms 812 KB Output is correct
5 Correct 718 ms 760 KB Output is correct
6 Correct 569 ms 752 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 684 ms 936 KB Output is correct
2 Correct 628 ms 788 KB Output is correct
3 Correct 1077 ms 640 KB Output is correct
4 Correct 788 ms 768 KB Output is correct
5 Correct 724 ms 640 KB Output is correct
6 Correct 490 ms 768 KB Output is correct
7 Correct 606 ms 768 KB Output is correct
8 Correct 2 ms 768 KB Output is correct
9 Correct 6 ms 776 KB Output is correct
10 Correct 1 ms 892 KB Output is correct
11 Correct 811 ms 768 KB Output is correct
12 Correct 537 ms 844 KB Output is correct
13 Correct 491 ms 760 KB Output is correct
14 Correct 484 ms 776 KB Output is correct
15 Correct 67 ms 708 KB Output is correct
16 Correct 85 ms 780 KB Output is correct
17 Correct 120 ms 908 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 830 ms 768 KB Output is correct
2 Correct 636 ms 768 KB Output is correct
3 Correct 611 ms 780 KB Output is correct
4 Correct 3 ms 888 KB Output is correct
5 Correct 4 ms 768 KB Output is correct
6 Correct 1 ms 652 KB Output is correct
7 Correct 646 ms 672 KB Output is correct
8 Correct 1162 ms 748 KB Output is correct
9 Correct 878 ms 640 KB Output is correct
10 Correct 829 ms 756 KB Output is correct
11 Correct 6 ms 672 KB Output is correct
12 Correct 6 ms 800 KB Output is correct
13 Correct 5 ms 768 KB Output is correct
14 Correct 4 ms 768 KB Output is correct
15 Correct 2 ms 712 KB Output is correct
16 Correct 541 ms 768 KB Output is correct
17 Correct 451 ms 640 KB Output is correct
18 Correct 427 ms 776 KB Output is correct
19 Correct 614 ms 640 KB Output is correct
20 Correct 651 ms 768 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 563 ms 896 KB Output is correct
2 Correct 555 ms 896 KB Output is correct
3 Correct 1037 ms 776 KB Output is correct
4 Correct 896 ms 640 KB Output is correct
5 Correct 806 ms 760 KB Output is correct
6 Correct 555 ms 792 KB Output is correct
7 Correct 542 ms 768 KB Output is correct
8 Correct 3 ms 904 KB Output is correct
9 Correct 7 ms 896 KB Output is correct
10 Correct 1 ms 768 KB Output is correct
11 Correct 592 ms 768 KB Output is correct
12 Correct 664 ms 776 KB Output is correct
13 Correct 1059 ms 760 KB Output is correct
14 Correct 805 ms 776 KB Output is correct
15 Correct 689 ms 768 KB Output is correct
16 Correct 505 ms 768 KB Output is correct
17 Correct 728 ms 896 KB Output is correct
18 Correct 523 ms 876 KB Output is correct
19 Correct 517 ms 896 KB Output is correct
20 Correct 653 ms 760 KB Output is correct
21 Correct 67 ms 768 KB Output is correct
22 Correct 85 ms 768 KB Output is correct
23 Correct 140 ms 896 KB Output is correct
24 Correct 7 ms 776 KB Output is correct
25 Correct 9 ms 776 KB Output is correct
26 Correct 7 ms 908 KB Output is correct
27 Correct 4 ms 896 KB Output is correct
28 Correct 2 ms 640 KB Output is correct
29 Correct 630 ms 768 KB Output is correct
30 Correct 525 ms 896 KB Output is correct
31 Correct 580 ms 768 KB Output is correct
32 Correct 566 ms 768 KB Output is correct
33 Correct 584 ms 640 KB Output is correct
34 Correct 380 ms 912 KB Output is correct
35 Correct 507 ms 792 KB Output is correct
36 Correct 581 ms 836 KB Output is correct
37 Correct 659 ms 892 KB Output is correct
38 Correct 584 ms 780 KB Output is correct
39 Correct 620 ms 896 KB Output is correct
40 Correct 643 ms 880 KB Output is correct
41 Correct 675 ms 796 KB Output is correct
42 Correct 93 ms 768 KB Output is correct
43 Correct 144 ms 708 KB Output is correct
44 Correct 172 ms 768 KB Output is correct
45 Correct 164 ms 904 KB Output is correct
46 Correct 380 ms 768 KB Output is correct
47 Correct 386 ms 952 KB Output is correct
48 Correct 72 ms 768 KB Output is correct
49 Correct 73 ms 896 KB Output is correct