답안 #1052135

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1052135	2024-08-10T12:03:28 Z	mychecksedad	기지국 (IOI20_stations)	C++17	100 / 100	553 ms	1192 KB

stations

#include "stations.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define pii pair<int,int>
#define ff first
#define ss second

void dfs(int v, int p, vector<vector<int>> &g, vi &tin, vi &tout, int &timer, vi &dep, vi &labels){
	dep[v] = dep[p] + 1;
	// if(dep[v] % 2) 
		tin[v] = timer++;
	for(int u: g[v]){
		if(u != p) dfs(u, v, g, tin, tout, timer, dep, labels);
	}
	// if(dep[v] % 2 == 0) 
		tout[v] = timer++;
}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	std::vector<int> labels(n);
	stack<int> s;
	vector<vector<int>> g(n);
	for(int i = 0; i < n-1; ++i){
		g[u[i]].pb(v[i]);
		g[v[i]].pb(u[i]);
	}

	vector<int> tin(n), tout(n);
	int timer = 0;
	vi dep(n);
	dfs(0, 0, g, tin, tout, timer, dep, labels);
	vector<int> val;
	for(int i = 0; i < n; ++i){
		if(dep[i] % 2) labels[i] = tin[i];
		else labels[i] = tout[i];
		val.pb(labels[i]);
	}
	sort(all(val));
	for(int &c: labels) c = lower_bound(all(val), c) - val.begin();
	// for(int i = 0; i < n; ++i) cout << tin[i] << ' '; cout << '\n';
	// for(int i = 0; i < n; ++i) cout << tout[i] << ' '; cout << '\n';
	// for(int i = 0; i < n; ++i) cout << labels[i] << ' '; cout << '\n';


	return labels;
}

int find_next_station(int s, int t, std::vector<int> c) {

	// cout << s << ' ';
	// for(int u: c) cout << u << ' '; cout << "qu\n";
	if(s < c[0]){
		if(t < s || t > c.back()){
			return c.back();
		}
		int val = *lower_bound(all(c), t);
		return val;
	}
	if(t > s || t < c[0]){
		return c[0];
	}
	int val = upper_bound(all(c), t) - c.begin(); --val;
	return c[val];
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	307 ms	940 KB	Output is correct
2	Correct	252 ms	940 KB	Output is correct
3	Correct	500 ms	684 KB	Output is correct
4	Correct	380 ms	684 KB	Output is correct
5	Correct	342 ms	684 KB	Output is correct
6	Correct	309 ms	1192 KB	Output is correct
7	Correct	233 ms	940 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	764 KB	Output is correct

Subtask #2
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	222 ms	684 KB	Output is correct
2	Correct	289 ms	772 KB	Output is correct
3	Correct	389 ms	684 KB	Output is correct
4	Correct	305 ms	764 KB	Output is correct
5	Correct	317 ms	768 KB	Output is correct
6	Correct	265 ms	684 KB	Output is correct

Subtask #3
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	298 ms	940 KB	Output is correct
2	Correct	260 ms	940 KB	Output is correct
3	Correct	528 ms	684 KB	Output is correct
4	Correct	375 ms	936 KB	Output is correct
5	Correct	296 ms	684 KB	Output is correct
6	Correct	245 ms	940 KB	Output is correct
7	Correct	244 ms	940 KB	Output is correct
8	Correct	1 ms	768 KB	Output is correct
9	Correct	1 ms	768 KB	Output is correct
10	Correct	0 ms	776 KB	Output is correct
11	Correct	320 ms	776 KB	Output is correct
12	Correct	246 ms	1020 KB	Output is correct
13	Correct	275 ms	1188 KB	Output is correct
14	Correct	278 ms	684 KB	Output is correct
15	Correct	20 ms	764 KB	Output is correct
16	Correct	27 ms	760 KB	Output is correct
17	Correct	53 ms	1008 KB	Output is correct

Subtask #4
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	541 ms	684 KB	Output is correct
2	Correct	393 ms	684 KB	Output is correct
3	Correct	337 ms	684 KB	Output is correct
4	Correct	2 ms	768 KB	Output is correct
5	Correct	2 ms	768 KB	Output is correct
6	Correct	0 ms	776 KB	Output is correct
7	Correct	345 ms	772 KB	Output is correct
8	Correct	553 ms	684 KB	Output is correct
9	Correct	405 ms	684 KB	Output is correct
10	Correct	330 ms	684 KB	Output is correct
11	Correct	2 ms	768 KB	Output is correct
12	Correct	1 ms	768 KB	Output is correct
13	Correct	1 ms	768 KB	Output is correct
14	Correct	1 ms	768 KB	Output is correct
15	Correct	0 ms	768 KB	Output is correct
16	Correct	325 ms	684 KB	Output is correct
17	Correct	293 ms	684 KB	Output is correct
18	Correct	276 ms	684 KB	Output is correct
19	Correct	267 ms	684 KB	Output is correct
20	Correct	221 ms	684 KB	Output is correct

Subtask #5
61.0 / 61.0

#	결과	실행 시간	메모리	Grader output
1	Correct	283 ms	940 KB	Output is correct
2	Correct	211 ms	948 KB	Output is correct
3	Correct	418 ms	684 KB	Output is correct
4	Correct	336 ms	688 KB	Output is correct
5	Correct	321 ms	684 KB	Output is correct
6	Correct	237 ms	940 KB	Output is correct
7	Correct	210 ms	684 KB	Output is correct
8	Correct	2 ms	772 KB	Output is correct
9	Correct	1 ms	768 KB	Output is correct
10	Correct	0 ms	768 KB	Output is correct
11	Correct	203 ms	684 KB	Output is correct
12	Correct	264 ms	684 KB	Output is correct
13	Correct	510 ms	684 KB	Output is correct
14	Correct	346 ms	684 KB	Output is correct
15	Correct	282 ms	768 KB	Output is correct
16	Correct	218 ms	684 KB	Output is correct
17	Correct	341 ms	684 KB	Output is correct
18	Correct	247 ms	1036 KB	Output is correct
19	Correct	257 ms	1020 KB	Output is correct
20	Correct	254 ms	684 KB	Output is correct
21	Correct	22 ms	764 KB	Output is correct
22	Correct	28 ms	764 KB	Output is correct
23	Correct	51 ms	744 KB	Output is correct
24	Correct	2 ms	768 KB	Output is correct
25	Correct	3 ms	768 KB	Output is correct
26	Correct	2 ms	768 KB	Output is correct
27	Correct	1 ms	768 KB	Output is correct
28	Correct	0 ms	768 KB	Output is correct
29	Correct	266 ms	772 KB	Output is correct
30	Correct	235 ms	684 KB	Output is correct
31	Correct	264 ms	684 KB	Output is correct
32	Correct	314 ms	684 KB	Output is correct
33	Correct	312 ms	684 KB	Output is correct
34	Correct	179 ms	940 KB	Output is correct
35	Correct	245 ms	940 KB	Output is correct
36	Correct	227 ms	940 KB	Output is correct
37	Correct	254 ms	764 KB	Output is correct
38	Correct	242 ms	684 KB	Output is correct
39	Correct	251 ms	768 KB	Output is correct
40	Correct	250 ms	776 KB	Output is correct
41	Correct	248 ms	932 KB	Output is correct
42	Correct	25 ms	768 KB	Output is correct
43	Correct	52 ms	1028 KB	Output is correct
44	Correct	83 ms	716 KB	Output is correct
45	Correct	79 ms	684 KB	Output is correct
46	Correct	152 ms	684 KB	Output is correct
47	Correct	169 ms	684 KB	Output is correct
48	Correct	28 ms	768 KB	Output is correct
49	Correct	26 ms	872 KB	Output is correct

답안 #1052135

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 8.0 / 8.0

Subtask #3 16.0 / 16.0

Subtask #4 10.0 / 10.0

Subtask #5 61.0 / 61.0

Subtask #1
5.0 / 5.0

Subtask #2
8.0 / 8.0

Subtask #3
16.0 / 16.0

Subtask #4
10.0 / 10.0

Subtask #5
61.0 / 61.0