Submission #404338

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
404338	2021-05-14T08:28:07 Z	AmineTrabelsi	Stations (IOI20_stations)	C++14	69.868 / 100	998 ms	776 KB

stations

#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
const int Mx = 1010;
int timer = 0;
void dfs(int node,int par,vector<int> &labels,vector<vector<int>> &tr,bool parity){
    if(!parity)labels[node] = timer++;
    else timer++;
    for(auto i:tr[node]){
        if(i != par){
            dfs(i,node,labels,tr,!parity);
        }
    }
    if(parity)labels[node] = timer++;
    else timer++;
}
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,labels,tr,0);
    for(auto &i:labels)i /=2;
	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	4 ms	432 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	320 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	617 ms	620 KB	Output is correct
2	Correct	527 ms	652 KB	Output is correct
3	Correct	912 ms	400 KB	Output is correct
4	Correct	828 ms	400 KB	Output is correct
5	Correct	583 ms	400 KB	Output is correct
6	Correct	614 ms	596 KB	Output is correct
7	Correct	489 ms	528 KB	Output is correct
8	Correct	4 ms	468 KB	Output is correct
9	Correct	4 ms	468 KB	Output is correct
10	Correct	2 ms	468 KB	Output is correct
11	Correct	643 ms	400 KB	Output is correct
12	Correct	554 ms	692 KB	Output is correct
13	Correct	558 ms	776 KB	Output is correct
14	Correct	499 ms	528 KB	Output is correct
15	Correct	71 ms	400 KB	Output is correct
16	Correct	71 ms	528 KB	Output is correct
17	Correct	111 ms	528 KB	Output is correct

Subtask #4

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	998 ms	400 KB	Output is correct
2	Correct	761 ms	520 KB	Output is correct
3	Correct	722 ms	484 KB	Output is correct
4	Correct	3 ms	468 KB	Output is correct
5	Correct	6 ms	476 KB	Output is correct
6	Correct	2 ms	476 KB	Output is correct
7	Correct	725 ms	528 KB	Output is correct
8	Correct	934 ms	400 KB	Output is correct
9	Correct	791 ms	400 KB	Output is correct
10	Correct	604 ms	488 KB	Output is correct
11	Correct	6 ms	468 KB	Output is correct
12	Correct	7 ms	472 KB	Output is correct
13	Correct	5 ms	472 KB	Output is correct
14	Correct	4 ms	464 KB	Output is correct
15	Correct	2 ms	476 KB	Output is correct
16	Correct	571 ms	520 KB	Output is correct
17	Correct	572 ms	484 KB	Output is correct
18	Correct	520 ms	484 KB	Output is correct
19	Correct	589 ms	400 KB	Output is correct
20	Correct	647 ms	488 KB	Output is correct

Subtask #5

43.868 / 61.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	696 ms	608 KB	Partially correct
2	Partially correct	552 ms	620 KB	Partially correct
3	Correct	850 ms	400 KB	Output is correct
4	Correct	685 ms	488 KB	Output is correct
5	Correct	728 ms	484 KB	Output is correct
6	Partially correct	538 ms	656 KB	Partially correct
7	Correct	555 ms	528 KB	Output is correct
8	Correct	3 ms	468 KB	Output is correct
9	Correct	5 ms	476 KB	Output is correct
10	Correct	2 ms	468 KB	Output is correct
11	Partially correct	659 ms	528 KB	Partially correct
12	Partially correct	591 ms	488 KB	Partially correct
13	Correct	982 ms	400 KB	Output is correct
14	Correct	657 ms	484 KB	Output is correct
15	Correct	690 ms	400 KB	Output is correct
16	Correct	615 ms	528 KB	Output is correct
17	Correct	671 ms	492 KB	Output is correct
18	Partially correct	464 ms	632 KB	Partially correct
19	Partially correct	526 ms	692 KB	Partially correct
20	Correct	582 ms	528 KB	Output is correct
21	Correct	76 ms	468 KB	Output is correct
22	Partially correct	93 ms	528 KB	Partially correct
23	Partially correct	150 ms	528 KB	Partially correct
24	Correct	5 ms	488 KB	Output is correct
25	Correct	7 ms	468 KB	Output is correct
26	Correct	5 ms	548 KB	Output is correct
27	Correct	5 ms	556 KB	Output is correct
28	Correct	2 ms	468 KB	Output is correct
29	Correct	691 ms	548 KB	Output is correct
30	Correct	649 ms	400 KB	Output is correct
31	Correct	679 ms	484 KB	Output is correct
32	Correct	553 ms	480 KB	Output is correct
33	Correct	542 ms	484 KB	Output is correct
34	Partially correct	439 ms	648 KB	Partially correct
35	Partially correct	539 ms	704 KB	Partially correct
36	Partially correct	493 ms	688 KB	Partially correct
37	Partially correct	497 ms	652 KB	Partially correct
38	Partially correct	620 ms	612 KB	Partially correct
39	Partially correct	561 ms	612 KB	Partially correct
40	Partially correct	457 ms	564 KB	Partially correct
41	Partially correct	530 ms	560 KB	Partially correct
42	Partially correct	68 ms	548 KB	Partially correct
43	Partially correct	115 ms	528 KB	Partially correct
44	Partially correct	189 ms	548 KB	Partially correct
45	Partially correct	202 ms	488 KB	Partially correct
46	Partially correct	413 ms	512 KB	Partially correct
47	Partially correct	363 ms	528 KB	Partially correct
48	Partially correct	70 ms	628 KB	Partially correct
49	Partially correct	66 ms	584 KB	Partially correct