Submission #404344

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
404344	2021-05-14T08:36:02 Z	AmineTrabelsi	Stations (IOI20_stations)	C++14	69.868 / 100	1123 ms	808 KB

stations

#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
const int Mx = 1010;
int timer = 0;
int tin[Mx],tout[Mx],lab[Mx];
void dfs(int node,int par,vector<vector<int>> &tr,bool parity){
    tin[node] = timer++;
    for(auto i:tr[node]){
        if(i != par){
            dfs(i,node,tr,!parity);
        }
    }
    tout[node] = timer++;
    lab[node] = (parity ? tin[node] : tout[node]) / 2;
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
    vector<int> labels(n);
    vector<vector<int>> tr(n+1,vector<int>(0));
	for (int i = 0; i < n-1; i++) {
		tr[u[i]].push_back(v[i]);
        tr[v[i]].push_back(u[i]);
	}
    dfs(0,-1,tr,1);
    for(int i=0;i<n;i++)labels[i] = lab[i];
	return labels;
}
int find_next_station(int s, int t, vector<int> c) {
    if ((int)c.size() == 1) return c.back();
    if (c.front() > s){
        // s in tin
        int l = s, r = c[(int)c.size() - 2];
        if (l > t || r < t) return c.back();
        int pos = lower_bound(c.begin(), c.end(), t) - c.begin();
        return c[pos];
    }
    // s is tout
    int l = c[1], r = s;
    if (l > t || r < t) return c.front();
    int pos = upper_bound(c.begin(), c.end(), t) - c.begin() - 1;
    return c[pos];
}

Subtask #1

0 / 5.0

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

Subtask #2

0 / 8.0

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

Subtask #3

16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	799 ms	668 KB	Output is correct
2	Correct	590 ms	596 KB	Output is correct
3	Correct	1099 ms	480 KB	Output is correct
4	Correct	819 ms	488 KB	Output is correct
5	Correct	759 ms	476 KB	Output is correct
6	Correct	552 ms	612 KB	Output is correct
7	Correct	558 ms	612 KB	Output is correct
8	Correct	3 ms	468 KB	Output is correct
9	Correct	5 ms	468 KB	Output is correct
10	Correct	2 ms	476 KB	Output is correct
11	Correct	662 ms	488 KB	Output is correct
12	Correct	585 ms	604 KB	Output is correct
13	Correct	573 ms	656 KB	Output is correct
14	Correct	492 ms	528 KB	Output is correct
15	Correct	51 ms	576 KB	Output is correct
16	Correct	60 ms	548 KB	Output is correct
17	Correct	154 ms	528 KB	Output is correct

Subtask #4

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1033 ms	548 KB	Output is correct
2	Correct	816 ms	484 KB	Output is correct
3	Correct	794 ms	400 KB	Output is correct
4	Correct	3 ms	468 KB	Output is correct
5	Correct	5 ms	468 KB	Output is correct
6	Correct	2 ms	468 KB	Output is correct
7	Correct	708 ms	488 KB	Output is correct
8	Correct	1041 ms	584 KB	Output is correct
9	Correct	822 ms	400 KB	Output is correct
10	Correct	662 ms	488 KB	Output is correct
11	Correct	7 ms	468 KB	Output is correct
12	Correct	8 ms	476 KB	Output is correct
13	Correct	4 ms	468 KB	Output is correct
14	Correct	4 ms	476 KB	Output is correct
15	Correct	2 ms	476 KB	Output is correct
16	Correct	582 ms	400 KB	Output is correct
17	Correct	666 ms	488 KB	Output is correct
18	Correct	567 ms	528 KB	Output is correct
19	Correct	628 ms	400 KB	Output is correct
20	Correct	603 ms	616 KB	Output is correct

Subtask #5

43.868 / 61.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	627 ms	616 KB	Partially correct
2	Partially correct	437 ms	528 KB	Partially correct
3	Correct	997 ms	480 KB	Output is correct
4	Correct	831 ms	468 KB	Output is correct
5	Correct	721 ms	488 KB	Output is correct
6	Partially correct	518 ms	528 KB	Partially correct
7	Correct	502 ms	608 KB	Output is correct
8	Correct	3 ms	476 KB	Output is correct
9	Correct	5 ms	472 KB	Output is correct
10	Correct	2 ms	468 KB	Output is correct
11	Partially correct	518 ms	528 KB	Partially correct
12	Partially correct	660 ms	528 KB	Partially correct
13	Correct	1123 ms	484 KB	Output is correct
14	Correct	792 ms	400 KB	Output is correct
15	Correct	718 ms	400 KB	Output is correct
16	Correct	520 ms	528 KB	Output is correct
17	Correct	815 ms	468 KB	Output is correct
18	Partially correct	537 ms	736 KB	Partially correct
19	Partially correct	500 ms	604 KB	Partially correct
20	Correct	479 ms	484 KB	Output is correct
21	Correct	54 ms	448 KB	Output is correct
22	Partially correct	105 ms	556 KB	Partially correct
23	Partially correct	151 ms	528 KB	Partially correct
24	Correct	7 ms	476 KB	Output is correct
25	Correct	9 ms	556 KB	Output is correct
26	Correct	6 ms	468 KB	Output is correct
27	Correct	4 ms	464 KB	Output is correct
28	Correct	3 ms	468 KB	Output is correct
29	Correct	658 ms	400 KB	Output is correct
30	Correct	562 ms	528 KB	Output is correct
31	Correct	606 ms	400 KB	Output is correct
32	Correct	500 ms	484 KB	Output is correct
33	Correct	612 ms	400 KB	Output is correct
34	Partially correct	411 ms	528 KB	Partially correct
35	Partially correct	431 ms	612 KB	Partially correct
36	Partially correct	453 ms	620 KB	Partially correct
37	Partially correct	485 ms	716 KB	Partially correct
38	Partially correct	544 ms	564 KB	Partially correct
39	Partially correct	570 ms	808 KB	Partially correct
40	Partially correct	484 ms	808 KB	Partially correct
41	Partially correct	538 ms	568 KB	Partially correct
42	Partially correct	89 ms	544 KB	Partially correct
43	Partially correct	152 ms	528 KB	Partially correct
44	Partially correct	178 ms	528 KB	Partially correct
45	Partially correct	147 ms	528 KB	Partially correct
46	Partially correct	323 ms	528 KB	Partially correct
47	Partially correct	325 ms	528 KB	Partially correct
48	Partially correct	52 ms	532 KB	Partially correct
49	Partially correct	82 ms	532 KB	Partially correct