Submission #408486

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
408486	2021-05-19T07:44:24 Z	muhammad_hokimiyon	Stations (IOI20_stations)	C++14	76 / 100	1784 ms	55780 KB

stations

#include "stations.h"
#include <vector>
#include<bits/stdc++.h>

#define fi first
#define se second

using namespace std;

const int N = 1e3 + 7;

vector<int> tin,tout,lv;

void dfs(vector<vector<int>> g, int x, int p, int &G)
{
    tin[x] = G++;
    for(auto y : g[x]){
        if(y == p)continue;
        lv[y] = 1 - lv[x];
        dfs(g, y, x, G);
    }
    tout[x] = G++;
}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	std::vector<int> labels(n);
	vector<vector<int>> g(n + 7);
	tin.resize(n + 7);
	tout.resize(n + 7);
	lv.resize(n + 7);
	for(int i = 0; i < n - 1; i++){
        int x = u[i], y = v[i];
        g[x].push_back(y);
        g[y].push_back(x);
	}
	int st = 0;
	dfs(g, 0, 0, st);
	for(int i = 0; i < n; i++){
        if(lv[i])labels[i] = tin[i];
        else labels[i] = tout[i];
	}
	return labels;
}

int find_next_station(int s, int t, std::vector<int> c) {
    if(s < c[0]){
        vector<pair<int, int>> nc;
        int ls = s;
        for(int i = 0; i + 1 < (int)c.size(); i++){
            nc.push_back({ls, c[i]});
            ls = c[i] + 1;
        }
        for(auto x : nc){
            if(x.fi <= t && t <= x.se){
                return x.se;
            }
        }
        return c.back();
    }else{
        assert(s > c.back());
        vector<pair<int, int>> nc;
        int ls = s - 1;
        for(int i = (int)c.size() - 1; i > 0; i--){
            nc.push_back({c[i], ls});
            ls = c[i] - 1;
        }
        for(auto x : nc){
            if(x.fi <= t && t <= x.se){
                return x.fi;
            }
        }
        return c[0];
    }
}

Subtask #1

0 / 5.0

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

Subtask #2

0 / 8.0

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

Subtask #3

16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1081 ms	55620 KB	Output is correct
2	Correct	1323 ms	53204 KB	Output is correct
3	Correct	1188 ms	400 KB	Output is correct
4	Correct	847 ms	400 KB	Output is correct
5	Correct	885 ms	528 KB	Output is correct
6	Correct	1250 ms	53612 KB	Output is correct
7	Correct	746 ms	42720 KB	Output is correct
8	Correct	3 ms	400 KB	Output is correct
9	Correct	6 ms	468 KB	Output is correct
10	Correct	2 ms	468 KB	Output is correct
11	Correct	829 ms	400 KB	Output is correct
12	Correct	1174 ms	54588 KB	Output is correct
13	Correct	1387 ms	50308 KB	Output is correct
14	Correct	643 ms	3144 KB	Output is correct
15	Correct	76 ms	504 KB	Output is correct
16	Correct	239 ms	668 KB	Output is correct
17	Correct	697 ms	740 KB	Output is correct

Subtask #4

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1625 ms	400 KB	Output is correct
2	Correct	728 ms	468 KB	Output is correct
3	Correct	730 ms	512 KB	Output is correct
4	Correct	5 ms	592 KB	Output is correct
5	Correct	7 ms	400 KB	Output is correct
6	Correct	3 ms	540 KB	Output is correct
7	Correct	817 ms	536 KB	Output is correct
8	Correct	1111 ms	400 KB	Output is correct
9	Correct	1281 ms	520 KB	Output is correct
10	Correct	933 ms	400 KB	Output is correct
11	Correct	7 ms	468 KB	Output is correct
12	Correct	6 ms	468 KB	Output is correct
13	Correct	7 ms	468 KB	Output is correct
14	Correct	7 ms	468 KB	Output is correct
15	Correct	3 ms	652 KB	Output is correct
16	Correct	687 ms	400 KB	Output is correct
17	Correct	647 ms	400 KB	Output is correct
18	Correct	605 ms	400 KB	Output is correct
19	Correct	898 ms	484 KB	Output is correct
20	Correct	1018 ms	424 KB	Output is correct

Subtask #5

50.0 / 61.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	1180 ms	55668 KB	Partially correct
2	Partially correct	1238 ms	48904 KB	Partially correct
3	Correct	1510 ms	464 KB	Output is correct
4	Correct	720 ms	404 KB	Output is correct
5	Correct	801 ms	400 KB	Output is correct
6	Partially correct	1652 ms	55628 KB	Partially correct
7	Partially correct	887 ms	31364 KB	Partially correct
8	Correct	3 ms	468 KB	Output is correct
9	Correct	7 ms	472 KB	Output is correct
10	Correct	2 ms	468 KB	Output is correct
11	Partially correct	1418 ms	1192 KB	Partially correct
12	Partially correct	1014 ms	1136 KB	Partially correct
13	Correct	1117 ms	468 KB	Output is correct
14	Correct	1125 ms	464 KB	Output is correct
15	Correct	855 ms	484 KB	Output is correct
16	Partially correct	708 ms	1176 KB	Partially correct
17	Correct	673 ms	400 KB	Output is correct
18	Partially correct	1287 ms	37508 KB	Partially correct
19	Partially correct	1283 ms	51672 KB	Partially correct
20	Partially correct	641 ms	4184 KB	Partially correct
21	Correct	88 ms	452 KB	Output is correct
22	Partially correct	300 ms	588 KB	Partially correct
23	Partially correct	870 ms	744 KB	Partially correct
24	Correct	5 ms	468 KB	Output is correct
25	Correct	5 ms	420 KB	Output is correct
26	Correct	6 ms	512 KB	Output is correct
27	Correct	6 ms	468 KB	Output is correct
28	Correct	2 ms	480 KB	Output is correct
29	Correct	653 ms	400 KB	Output is correct
30	Correct	738 ms	484 KB	Output is correct
31	Correct	734 ms	484 KB	Output is correct
32	Correct	665 ms	660 KB	Output is correct
33	Correct	622 ms	400 KB	Output is correct
34	Partially correct	1027 ms	42232 KB	Partially correct
35	Partially correct	1525 ms	55780 KB	Partially correct
36	Partially correct	1347 ms	46020 KB	Partially correct
37	Partially correct	1301 ms	13592 KB	Partially correct
38	Partially correct	1283 ms	13640 KB	Partially correct
39	Partially correct	1331 ms	18044 KB	Partially correct
40	Partially correct	1347 ms	17780 KB	Partially correct
41	Partially correct	1784 ms	14588 KB	Partially correct
42	Partially correct	459 ms	688 KB	Partially correct
43	Partially correct	661 ms	740 KB	Partially correct
44	Partially correct	636 ms	1056 KB	Partially correct
45	Partially correct	860 ms	1588 KB	Partially correct
46	Partially correct	974 ms	13824 KB	Partially correct
47	Partially correct	1293 ms	26944 KB	Partially correct
48	Partially correct	544 ms	1092 KB	Partially correct
49	Partially correct	684 ms	1420 KB	Partially correct