답안 #804866

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
804866	2023-08-03T11:42:17 Z	alvingogo	기지국 (IOI20_stations)	C++14	100 / 100	812 ms	764 KB

stations

#include "stations.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

struct TR{
	struct no{
		vector<int> ch;
		int lb=-1;
	};
	vector<no> v;
	void init(int x){
		v.resize(x);
	}
	void add(int x,int y){
		v[x].ch.push_back(y);
		v[y].ch.push_back(x);
	}
	int cnt=0;
	void dfs(int r,int f,int d){
		if(d%2==0){
			v[r].lb=cnt;
			cnt++;
		}
		for(auto h:v[r].ch){
			if(h!=f){
				dfs(h,r,d+1);
			}
		}
		if(d%2){
			v[r].lb=cnt;
			cnt++;
		}
	}
};
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	TR tr;
	tr.init(n);
	for(int i=0;i<n-1;i++){
		tr.add(u[i],v[i]);
	}
	tr.dfs(0,0,0);
	vector<int> labels(n);
	for (int i = 0; i < n; i++) {
		labels[i] = tr.v[i].lb;
	}
	return labels;
}

int find_next_station(int s, int t, vector<int> c) {
	for(auto h:c){
		if(h==t){
			return h;
		}
	}
	if(c.size()==1){
		return c[0];
	}
	sort(c.begin(),c.end());
	if(s<c[0]){
		for(auto h:c){
			if(t>=s && t<=h){
				return h;
			}
		}
		return c.back();
	}
	else{
		reverse(c.begin(),c.end());
		for(auto h:c){
			if(t<=s && t>=h){
				return h;
			}
		}
		return c.back();
	}
}

Subtask #1

5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	370 ms	548 KB	Output is correct
2	Correct	373 ms	548 KB	Output is correct
3	Correct	582 ms	500 KB	Output is correct
4	Correct	534 ms	548 KB	Output is correct
5	Correct	470 ms	544 KB	Output is correct
6	Correct	348 ms	568 KB	Output is correct
7	Correct	415 ms	676 KB	Output is correct
8	Correct	2 ms	492 KB	Output is correct
9	Correct	3 ms	492 KB	Output is correct
10	Correct	0 ms	488 KB	Output is correct

Subtask #2

8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	384 ms	508 KB	Output is correct
2	Correct	423 ms	544 KB	Output is correct
3	Correct	580 ms	504 KB	Output is correct
4	Correct	564 ms	508 KB	Output is correct
5	Correct	431 ms	504 KB	Output is correct
6	Correct	405 ms	492 KB	Output is correct

Subtask #3

16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	442 ms	548 KB	Output is correct
2	Correct	301 ms	716 KB	Output is correct
3	Correct	727 ms	504 KB	Output is correct
4	Correct	547 ms	504 KB	Output is correct
5	Correct	554 ms	420 KB	Output is correct
6	Correct	440 ms	512 KB	Output is correct
7	Correct	465 ms	524 KB	Output is correct
8	Correct	1 ms	564 KB	Output is correct
9	Correct	4 ms	496 KB	Output is correct
10	Correct	1 ms	492 KB	Output is correct
11	Correct	601 ms	416 KB	Output is correct
12	Correct	434 ms	588 KB	Output is correct
13	Correct	409 ms	628 KB	Output is correct
14	Correct	342 ms	568 KB	Output is correct
15	Correct	48 ms	444 KB	Output is correct
16	Correct	61 ms	548 KB	Output is correct
17	Correct	94 ms	508 KB	Output is correct

Subtask #4

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	781 ms	424 KB	Output is correct
2	Correct	601 ms	420 KB	Output is correct
3	Correct	464 ms	544 KB	Output is correct
4	Correct	2 ms	500 KB	Output is correct
5	Correct	3 ms	500 KB	Output is correct
6	Correct	0 ms	476 KB	Output is correct
7	Correct	430 ms	504 KB	Output is correct
8	Correct	778 ms	508 KB	Output is correct
9	Correct	511 ms	500 KB	Output is correct
10	Correct	461 ms	512 KB	Output is correct
11	Correct	3 ms	472 KB	Output is correct
12	Correct	3 ms	492 KB	Output is correct
13	Correct	4 ms	492 KB	Output is correct
14	Correct	2 ms	496 KB	Output is correct
15	Correct	1 ms	444 KB	Output is correct
16	Correct	409 ms	420 KB	Output is correct
17	Correct	401 ms	416 KB	Output is correct
18	Correct	350 ms	416 KB	Output is correct
19	Correct	327 ms	500 KB	Output is correct
20	Correct	365 ms	416 KB	Output is correct

Subtask #5

61.0 / 61.0

#	결과	실행 시간	메모리	Grader output
1	Correct	365 ms	504 KB	Output is correct
2	Correct	447 ms	572 KB	Output is correct
3	Correct	812 ms	500 KB	Output is correct
4	Correct	451 ms	532 KB	Output is correct
5	Correct	575 ms	508 KB	Output is correct
6	Correct	323 ms	544 KB	Output is correct
7	Correct	313 ms	548 KB	Output is correct
8	Correct	1 ms	492 KB	Output is correct
9	Correct	4 ms	492 KB	Output is correct
10	Correct	0 ms	500 KB	Output is correct
11	Correct	406 ms	576 KB	Output is correct
12	Correct	413 ms	548 KB	Output is correct
13	Correct	767 ms	420 KB	Output is correct
14	Correct	640 ms	504 KB	Output is correct
15	Correct	482 ms	420 KB	Output is correct
16	Correct	383 ms	512 KB	Output is correct
17	Correct	529 ms	420 KB	Output is correct
18	Correct	373 ms	752 KB	Output is correct
19	Correct	453 ms	584 KB	Output is correct
20	Correct	361 ms	500 KB	Output is correct
21	Correct	51 ms	492 KB	Output is correct
22	Correct	63 ms	576 KB	Output is correct
23	Correct	94 ms	544 KB	Output is correct
24	Correct	5 ms	492 KB	Output is correct
25	Correct	3 ms	492 KB	Output is correct
26	Correct	2 ms	496 KB	Output is correct
27	Correct	2 ms	492 KB	Output is correct
28	Correct	1 ms	500 KB	Output is correct
29	Correct	503 ms	416 KB	Output is correct
30	Correct	465 ms	416 KB	Output is correct
31	Correct	462 ms	504 KB	Output is correct
32	Correct	347 ms	500 KB	Output is correct
33	Correct	435 ms	420 KB	Output is correct
34	Correct	264 ms	508 KB	Output is correct
35	Correct	261 ms	628 KB	Output is correct
36	Correct	364 ms	704 KB	Output is correct
37	Correct	420 ms	604 KB	Output is correct
38	Correct	407 ms	664 KB	Output is correct
39	Correct	373 ms	744 KB	Output is correct
40	Correct	392 ms	764 KB	Output is correct
41	Correct	363 ms	588 KB	Output is correct
42	Correct	59 ms	572 KB	Output is correct
43	Correct	91 ms	504 KB	Output is correct
44	Correct	110 ms	544 KB	Output is correct
45	Correct	119 ms	544 KB	Output is correct
46	Correct	301 ms	548 KB	Output is correct
47	Correct	257 ms	676 KB	Output is correct
48	Correct	46 ms	564 KB	Output is correct
49	Correct	42 ms	672 KB	Output is correct