Submission #586045

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
586045	2022-06-29T18:44:28 Z	wdjpng	Stations (IOI20_stations)	C++17	5 / 100	895 ms	796 KB

stations

#include<bits/stdc++.h>

#include "stations.h"

using namespace std;
#define rep(i,n) for(int i = 0; i<((int)n);i++)

int c;
vector<vector<int>>E;
vector<int>pre;
void dfs(int v, int p)
{
	pre[v]=c++;
	for(int w : E[v]) if(w!=p) dfs(w,v);
}

vector<int> label(int n, int k, std::vector<int> u, vector<int> v) {
	E=vector<vector<int>>(n);
	pre.assign(n,-1);
	c=0;
	rep(i,n-1) {E[u[i]].push_back(v[i]); E[v[i]].push_back(u[i]);}

	rep(i,n) if(E[i].size()==1) {dfs(i,-1); break;}

	return pre;
}

int find_next_station(int s, int t, vector<int> r) {
	vector<int>b=r;
	sort(b.begin(),b.end());
	rep(i,b.size()-1) if(b[i+1]>t) return b[i];
	return b[b.size()-1];
}

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	523 ms	544 KB	Output is correct
2	Correct	384 ms	636 KB	Output is correct
3	Correct	895 ms	420 KB	Output is correct
4	Correct	637 ms	548 KB	Output is correct
5	Correct	561 ms	500 KB	Output is correct
6	Correct	473 ms	544 KB	Output is correct
7	Correct	390 ms	496 KB	Output is correct
8	Correct	2 ms	496 KB	Output is correct
9	Correct	3 ms	500 KB	Output is correct
10	Correct	0 ms	492 KB	Output is correct

Subtask #2

0 / 8.0

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

Subtask #3

0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	510 ms	632 KB	Output is correct
2	Correct	471 ms	676 KB	Output is correct
3	Correct	797 ms	484 KB	Output is correct
4	Correct	697 ms	504 KB	Output is correct
5	Correct	604 ms	504 KB	Output is correct
6	Correct	421 ms	628 KB	Output is correct
7	Correct	418 ms	548 KB	Output is correct
8	Correct	1 ms	492 KB	Output is correct
9	Correct	6 ms	492 KB	Output is correct
10	Correct	1 ms	496 KB	Output is correct
11	Correct	608 ms	504 KB	Output is correct
12	Incorrect	405 ms	744 KB	Wrong query response.
13	Halted	0 ms	0 KB	-

Subtask #4

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	850 ms	488 KB	Output is correct
2	Correct	632 ms	500 KB	Output is correct
3	Correct	511 ms	416 KB	Output is correct
4	Correct	2 ms	504 KB	Output is correct
5	Correct	2 ms	492 KB	Output is correct
6	Correct	1 ms	492 KB	Output is correct
7	Correct	489 ms	416 KB	Output is correct
8	Correct	813 ms	512 KB	Output is correct
9	Correct	619 ms	548 KB	Output is correct
10	Correct	536 ms	416 KB	Output is correct
11	Incorrect	5 ms	500 KB	Wrong query response.
12	Halted	0 ms	0 KB	-

Subtask #5

0 / 61.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	493 ms	636 KB	Output is correct
2	Correct	450 ms	796 KB	Output is correct
3	Correct	836 ms	416 KB	Output is correct
4	Correct	625 ms	416 KB	Output is correct
5	Correct	533 ms	420 KB	Output is correct
6	Correct	487 ms	620 KB	Output is correct
7	Correct	385 ms	504 KB	Output is correct
8	Correct	4 ms	500 KB	Output is correct
9	Correct	3 ms	492 KB	Output is correct
10	Correct	0 ms	492 KB	Output is correct
11	Incorrect	465 ms	632 KB	Wrong query response.
12	Halted	0 ms	0 KB	-