Submission #381708

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
381708	2021-03-25T18:04:07 Z	b00n0rp	Stations (IOI20_stations)	C++17	5 / 100	1178 ms	1268 KB

stations

#include<bits/stdc++.h>
#include "stations.h"

using namespace std;

#define vi vector<int>
#define pb push_back
#define REP(i,n) for(int i = 0; i < n; i ++)
#define FOR(i,a,b) for(int i = a; i < b; i ++)

const int MAXN = 1005;

int st[MAXN],fin[MAXN],dep[MAXN],tim = 0;
vi adj[MAXN];

void dfs(int u,int p,int d){
	if(d%2 == 0) st[u] = tim++;
	dep[u] = d;
	for(auto v:adj[u]){
		if(v != p) dfs(v,u,d+1);
	}
	if(d%2 == 1) fin[u] = tim++;
}

vi label(int n, int k, vi u, vi v){
	tim = 0;
	REP(i,n) adj[i].clear();
	vi labels(n);
	REP(i,n-1){
		adj[u[i]].pb(v[i]);
		adj[v[i]].pb(u[i]);
	}
	dfs(0,0,0);
	for (int i = 0; i < n; i++){
		if(dep[i]%2 == 0) labels[i] = st[i];
		else labels[i] = fin[i];
	}
	return labels;
}

int find_next_station(int s, int t, vi c){
	if(c.size() == 1) return c[0];
	for(auto x:c){
		if(x == t) return x;
	}
	sort(c.begin(),c.end());
	if(s < c[0]){
		if(t < s) return c.back();
		for(auto x:c){
			if(t < x) return x;
		}
		return c.back();
	}
	else{
		if(t > s) return c[0];
		for(auto x:c){
			if(x != c[0] and t > x) return x;
		}
		return c[0];
	}
}

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	614 ms	864 KB	Output is correct
2	Correct	456 ms	1112 KB	Output is correct
3	Correct	929 ms	736 KB	Output is correct
4	Correct	725 ms	948 KB	Output is correct
5	Correct	597 ms	864 KB	Output is correct
6	Correct	487 ms	1084 KB	Output is correct
7	Correct	479 ms	1096 KB	Output is correct
8	Correct	4 ms	948 KB	Output is correct
9	Correct	6 ms	736 KB	Output is correct
10	Correct	2 ms	736 KB	Output is correct

Subtask #2

0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	531 ms	1268 KB	Wrong query response.
2	Halted	0 ms	0 KB	-

Subtask #3

0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	547 ms	1192 KB	Output is correct
2	Correct	431 ms	864 KB	Output is correct
3	Correct	959 ms	864 KB	Output is correct
4	Correct	822 ms	948 KB	Output is correct
5	Correct	711 ms	948 KB	Output is correct
6	Correct	524 ms	1076 KB	Output is correct
7	Correct	519 ms	1108 KB	Output is correct
8	Correct	4 ms	940 KB	Output is correct
9	Correct	5 ms	864 KB	Output is correct
10	Correct	2 ms	948 KB	Output is correct
11	Correct	667 ms	1076 KB	Output is correct
12	Correct	545 ms	1204 KB	Output is correct
13	Incorrect	492 ms	1132 KB	Wrong query response.
14	Halted	0 ms	0 KB	-

Subtask #4

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	933 ms	864 KB	Output is correct
2	Correct	678 ms	1108 KB	Output is correct
3	Correct	778 ms	884 KB	Output is correct
4	Correct	3 ms	980 KB	Output is correct
5	Correct	6 ms	864 KB	Output is correct
6	Correct	2 ms	736 KB	Output is correct
7	Correct	786 ms	864 KB	Output is correct
8	Correct	1178 ms	940 KB	Output is correct
9	Correct	718 ms	1108 KB	Output is correct
10	Correct	798 ms	832 KB	Output is correct
11	Correct	7 ms	948 KB	Output is correct
12	Correct	6 ms	736 KB	Output is correct
13	Correct	5 ms	884 KB	Output is correct
14	Correct	4 ms	940 KB	Output is correct
15	Correct	3 ms	864 KB	Output is correct
16	Incorrect	508 ms	940 KB	Wrong query response.
17	Halted	0 ms	0 KB	-

Subtask #5

0 / 61.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	526 ms	960 KB	Output is correct
2	Correct	587 ms	992 KB	Output is correct
3	Correct	1079 ms	948 KB	Output is correct
4	Correct	710 ms	800 KB	Output is correct
5	Correct	666 ms	948 KB	Output is correct
6	Correct	517 ms	888 KB	Output is correct
7	Correct	554 ms	1236 KB	Output is correct
8	Correct	4 ms	736 KB	Output is correct
9	Correct	6 ms	736 KB	Output is correct
10	Correct	2 ms	864 KB	Output is correct
11	Incorrect	453 ms	876 KB	Wrong query response.
12	Halted	0 ms	0 KB	-