Submission #397934

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
397934	2021-05-03T12:00:32 Z	cfalas	Stations (IOI20_stations)	C++14	76 / 100	1154 ms	788 KB

stations

#include "stations.h"
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define INF 10000000
#define MOD 1000000007
#define MID ((l+r)/2)
#define HASHMOD 2305843009213693951
#define ll long long
#define ull unsigned long long
#define F first
#define S second
typedef pair<ll, ll> ii;
typedef pair<ii, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef map<int, int> mii;

#define EPS 1e-6
#define FOR(i,n) for(int i=0;i<((int)(n));i++)
#define FORi(i,a,b) for(int i=((int)(a));i<((int)(b));i++)
#define FOA(v, a) for(auto v : a)

vector<vi> adj;
vi labels;
int cnt=0;
vi sub;
int d=0;
void dfs(int s, int p=-1){
	d++;
	//cout<<"enter "<<s<<" "<<cnt<<endl;
	labels[s] = cnt++;
	for(auto v : adj[s]) if(v!=p) dfs(v, s), sub[s]+=sub[v];
	d--;
	//cout<<"leave "<<s<<" "<<cnt<<endl;
	if(d%2==1) labels[s] = cnt;
	cnt++;

}

vi label(int n, int k, std::vector<int> u, std::vector<int> v) {
	cnt = 0;
	adj.assign(n, vi());
	sub.assign(n, 1);
	labels.assign(n, 0);
	FOR(i,n-1){
		adj[u[i]].push_back(v[i]);
		adj[v[i]].push_back(u[i]);
	}
	dfs(0);
	//FOR(i,n) cout<<labels[i]<<" "<<sub[i]-1<<endl;

	//FOA(v, labels) cout<<v<<" "; cout<<endl;

	return labels;
}

int find_next_station(int s, int t, std::vector<int> c) {
	sort(c.begin(), c.end());
	if(s<c[0]){
		// s is t_in
		// c is t_out
		//cout<<s<<" "<<t<<endl;
		int prev = s;
		FOA(v,c){
			if(prev<t && t<=v) return v;
			prev = v;
		}
		return c.back();
	}
	else{
		// s is t_out
		// c is t_in
		//cout<<s<<" "<<t<<endl;
		reverse(c.begin(), c.end());
		//cout<<"N: "; FOA(v,c) cout<<v<<" ";
		//cout<<endl;
		int prev = s;
		FOA(v,c){
			if(v<=t && t<prev) return v;
			prev = v;
		}
		return c.back();
	}
}

Subtask #1

0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	3 ms	452 KB	Invalid labels (values out of range). scenario=2, k=1000, vertex=1, label=1990
2	Halted	0 ms	0 KB	-

Subtask #2

0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	5 ms	320 KB	Invalid labels (values out of range). scenario=0, k=1000, vertex=1, label=1022
2	Halted	0 ms	0 KB	-

Subtask #3

16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	676 ms	704 KB	Output is correct
2	Correct	577 ms	636 KB	Output is correct
3	Correct	1000 ms	400 KB	Output is correct
4	Correct	761 ms	488 KB	Output is correct
5	Correct	808 ms	488 KB	Output is correct
6	Correct	518 ms	604 KB	Output is correct
7	Correct	554 ms	556 KB	Output is correct
8	Correct	3 ms	472 KB	Output is correct
9	Correct	4 ms	472 KB	Output is correct
10	Correct	2 ms	472 KB	Output is correct
11	Correct	681 ms	496 KB	Output is correct
12	Correct	546 ms	612 KB	Output is correct
13	Correct	570 ms	696 KB	Output is correct
14	Correct	587 ms	528 KB	Output is correct
15	Correct	52 ms	452 KB	Output is correct
16	Correct	90 ms	548 KB	Output is correct
17	Correct	136 ms	528 KB	Output is correct

Subtask #4

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	972 ms	400 KB	Output is correct
2	Correct	865 ms	496 KB	Output is correct
3	Correct	769 ms	528 KB	Output is correct
4	Correct	3 ms	484 KB	Output is correct
5	Correct	7 ms	472 KB	Output is correct
6	Correct	2 ms	480 KB	Output is correct
7	Correct	670 ms	492 KB	Output is correct
8	Correct	1154 ms	492 KB	Output is correct
9	Correct	898 ms	400 KB	Output is correct
10	Correct	737 ms	516 KB	Output is correct
11	Correct	5 ms	472 KB	Output is correct
12	Correct	7 ms	472 KB	Output is correct
13	Correct	5 ms	480 KB	Output is correct
14	Correct	5 ms	472 KB	Output is correct
15	Correct	2 ms	480 KB	Output is correct
16	Correct	722 ms	496 KB	Output is correct
17	Correct	579 ms	404 KB	Output is correct
18	Correct	682 ms	492 KB	Output is correct
19	Correct	613 ms	504 KB	Output is correct
20	Correct	576 ms	420 KB	Output is correct

Subtask #5

50.0 / 61.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	581 ms	648 KB	Partially correct
2	Partially correct	452 ms	620 KB	Partially correct
3	Correct	1022 ms	400 KB	Output is correct
4	Correct	967 ms	532 KB	Output is correct
5	Correct	715 ms	400 KB	Output is correct
6	Partially correct	546 ms	616 KB	Partially correct
7	Partially correct	634 ms	528 KB	Partially correct
8	Correct	2 ms	480 KB	Output is correct
9	Correct	4 ms	452 KB	Output is correct
10	Correct	2 ms	472 KB	Output is correct
11	Partially correct	587 ms	604 KB	Partially correct
12	Partially correct	526 ms	528 KB	Partially correct
13	Correct	1019 ms	520 KB	Output is correct
14	Correct	817 ms	400 KB	Output is correct
15	Correct	556 ms	492 KB	Output is correct
16	Partially correct	492 ms	528 KB	Partially correct
17	Correct	734 ms	492 KB	Output is correct
18	Partially correct	485 ms	716 KB	Partially correct
19	Partially correct	496 ms	688 KB	Partially correct
20	Partially correct	445 ms	520 KB	Partially correct
21	Correct	57 ms	420 KB	Output is correct
22	Partially correct	94 ms	540 KB	Partially correct
23	Partially correct	153 ms	528 KB	Partially correct
24	Correct	7 ms	468 KB	Output is correct
25	Correct	5 ms	472 KB	Output is correct
26	Correct	5 ms	472 KB	Output is correct
27	Correct	4 ms	472 KB	Output is correct
28	Correct	2 ms	480 KB	Output is correct
29	Correct	706 ms	496 KB	Output is correct
30	Correct	722 ms	488 KB	Output is correct
31	Correct	609 ms	488 KB	Output is correct
32	Correct	508 ms	400 KB	Output is correct
33	Correct	579 ms	400 KB	Output is correct
34	Partially correct	384 ms	620 KB	Partially correct
35	Partially correct	556 ms	684 KB	Partially correct
36	Partially correct	576 ms	696 KB	Partially correct
37	Partially correct	557 ms	604 KB	Partially correct
38	Partially correct	598 ms	684 KB	Partially correct
39	Partially correct	576 ms	676 KB	Partially correct
40	Partially correct	522 ms	608 KB	Partially correct
41	Partially correct	449 ms	700 KB	Partially correct
42	Partially correct	62 ms	528 KB	Partially correct
43	Partially correct	124 ms	708 KB	Partially correct
44	Partially correct	123 ms	528 KB	Partially correct
45	Partially correct	176 ms	528 KB	Partially correct
46	Partially correct	390 ms	528 KB	Partially correct
47	Partially correct	408 ms	528 KB	Partially correct
48	Partially correct	65 ms	528 KB	Partially correct
49	Partially correct	72 ms	788 KB	Partially correct