Submission #334138

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
334138	2020-12-08T12:01:00 Z	rocks03	Stations (IOI20_stations)	C++14	52.3244 / 100	1005 ms	1180 KB

stations

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define pb push_back
#define SZ(x) ((int)(x).size())
#define all(x) x.begin(), x.end()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int M = 1000;
int timer;
vector<vector<int>> g;

void dfs(int v, int p, vector<int>& labels){
    int in = timer;
    for(auto u : g[v]){
        if(u == p)
            continue;
        dfs(u, v, labels);
    }
    int ou = timer++;
    labels[v] = (M*in + ou);
}

vector<int> label(int n, int k, vector<int> u, vector<int> v){
	g.resize(n);
	for(int i = 0; i < n; i++){
        g[i].clear();
	}
	for(int i = 0; i < n-1; i++){
	    g[u[i]].pb(v[i]);
	    g[v[i]].pb(u[i]);
	}
	vector<int> labels(n);
    timer = 0;
	dfs(0, -1, labels);
	return labels;
}

int find_next_station(int s, int t, vector<int> c){
	int in_s = s / M, ou_s = s % M;
	int in_t = t / M, ou_t = t % M;
	int id = -1;
	for(auto x : c){
	    int in_x = x / M, ou_x = x % M;
	    if(in_x <= in_s && ou_s <= ou_x){
	        id = x;
	        continue;
	    }
	    if(in_x <= in_t && ou_t <= ou_x){
	        return x;
	    }
	}
	return id;
}

Subtask #1

0 / 5.0

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

Subtask #2

0 / 8.0

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

Subtask #3

16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	572 ms	864 KB	Output is correct
2	Correct	602 ms	884 KB	Output is correct
3	Correct	988 ms	756 KB	Output is correct
4	Correct	680 ms	992 KB	Output is correct
5	Correct	578 ms	1000 KB	Output is correct
6	Correct	515 ms	964 KB	Output is correct
7	Correct	466 ms	992 KB	Output is correct
8	Correct	3 ms	756 KB	Output is correct
9	Correct	5 ms	736 KB	Output is correct
10	Correct	1 ms	736 KB	Output is correct
11	Correct	610 ms	864 KB	Output is correct
12	Correct	533 ms	964 KB	Output is correct
13	Correct	534 ms	1076 KB	Output is correct
14	Correct	489 ms	928 KB	Output is correct
15	Correct	59 ms	856 KB	Output is correct
16	Correct	69 ms	756 KB	Output is correct
17	Correct	111 ms	784 KB	Output is correct

Subtask #4

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	882 ms	736 KB	Output is correct
2	Correct	660 ms	756 KB	Output is correct
3	Correct	638 ms	872 KB	Output is correct
4	Correct	2 ms	736 KB	Output is correct
5	Correct	4 ms	872 KB	Output is correct
6	Correct	2 ms	756 KB	Output is correct
7	Correct	657 ms	756 KB	Output is correct
8	Correct	931 ms	872 KB	Output is correct
9	Correct	699 ms	992 KB	Output is correct
10	Correct	650 ms	992 KB	Output is correct
11	Correct	6 ms	756 KB	Output is correct
12	Correct	6 ms	736 KB	Output is correct
13	Correct	5 ms	756 KB	Output is correct
14	Correct	3 ms	872 KB	Output is correct
15	Correct	2 ms	736 KB	Output is correct
16	Correct	504 ms	736 KB	Output is correct
17	Correct	535 ms	864 KB	Output is correct
18	Correct	525 ms	736 KB	Output is correct
19	Correct	583 ms	872 KB	Output is correct
20	Correct	631 ms	864 KB	Output is correct

Subtask #5

26.3244 / 61.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	635 ms	864 KB	Partially correct
2	Partially correct	472 ms	956 KB	Partially correct
3	Correct	1005 ms	864 KB	Output is correct
4	Partially correct	736 ms	1012 KB	Partially correct
5	Partially correct	635 ms	992 KB	Partially correct
6	Partially correct	483 ms	884 KB	Partially correct
7	Partially correct	581 ms	1008 KB	Partially correct
8	Partially correct	4 ms	992 KB	Partially correct
9	Correct	4 ms	736 KB	Output is correct
10	Partially correct	2 ms	756 KB	Partially correct
11	Partially correct	465 ms	736 KB	Partially correct
12	Partially correct	537 ms	1004 KB	Partially correct
13	Correct	928 ms	1000 KB	Output is correct
14	Partially correct	757 ms	756 KB	Partially correct
15	Partially correct	634 ms	864 KB	Partially correct
16	Partially correct	579 ms	800 KB	Partially correct
17	Partially correct	594 ms	864 KB	Partially correct
18	Partially correct	509 ms	1000 KB	Partially correct
19	Partially correct	520 ms	1064 KB	Partially correct
20	Partially correct	471 ms	792 KB	Partially correct
21	Partially correct	57 ms	864 KB	Partially correct
22	Partially correct	84 ms	736 KB	Partially correct
23	Partially correct	111 ms	756 KB	Partially correct
24	Partially correct	7 ms	756 KB	Partially correct
25	Partially correct	6 ms	736 KB	Partially correct
26	Partially correct	6 ms	736 KB	Partially correct
27	Partially correct	4 ms	864 KB	Partially correct
28	Partially correct	2 ms	756 KB	Partially correct
29	Partially correct	559 ms	756 KB	Partially correct
30	Partially correct	484 ms	864 KB	Partially correct
31	Partially correct	493 ms	1012 KB	Partially correct
32	Partially correct	619 ms	756 KB	Partially correct
33	Partially correct	532 ms	872 KB	Partially correct
34	Partially correct	396 ms	1140 KB	Partially correct
35	Partially correct	465 ms	992 KB	Partially correct
36	Partially correct	438 ms	1180 KB	Partially correct
37	Partially correct	499 ms	1104 KB	Partially correct
38	Partially correct	443 ms	1104 KB	Partially correct
39	Partially correct	554 ms	992 KB	Partially correct
40	Partially correct	546 ms	992 KB	Partially correct
41	Partially correct	613 ms	992 KB	Partially correct
42	Partially correct	62 ms	916 KB	Partially correct
43	Partially correct	116 ms	736 KB	Partially correct
44	Partially correct	172 ms	764 KB	Partially correct
45	Partially correct	182 ms	764 KB	Partially correct
46	Partially correct	340 ms	736 KB	Partially correct
47	Partially correct	356 ms	1008 KB	Partially correct
48	Partially correct	70 ms	1096 KB	Partially correct
49	Partially correct	67 ms	992 KB	Partially correct