Submission #306771

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
306771	2020-09-26T08:58:01 Z	VEGAnn	Stations (IOI20_stations)	C++14	52.3205 / 100	1007 ms	1132 KB

stations

#include "stations.h"
#include <bits/stdc++.h>
#define PB push_back
#define sz(x) ((int)x.size())
using namespace std;
vector<int> g[1000];
int tin[1000], tout[1000], tt = 0;

void dfs(int v, int p){
    tin[v] = tt++;

    for (int u : g[v]){
        if (u == p) continue;
        dfs(u, v);
    }

    tout[v] = tt - 1;
}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
    for (int i = 0; i < n; i++)
        g[i].clear();

    tt = 0;

    for (int i = 0; i < sz(u); i++){
        g[u[i]].PB(v[i]);
        g[v[i]].PB(u[i]);
    }

    dfs(0, -1);

    vector<int> labels;

    labels.resize(n);

    for (int i = 0; i < n; i++) {
        labels[i] = tin[i] * 1000 + tout[i];
        assert(labels[i] <= k);
    }

	return labels;
}

int find_next_station(int s, int t, std::vector<int> c) {
    int N = 1000;

    int tin_s = s / N;
    int tout_s = s % N;

    int tin_t = t / N;
    int tout_t = t % N;

    if (tin_s <= tin_t && tout_s >= tout_t){
        for (int v : c) {
            int tin_v = v / N;
            int tout_v = v % N;

            if (tin_v > tin_s && tin_v <= tin_t && tout_v >= tout_t)
                return v;
        }
    } else {
        for (int v : c)
            if (v / N < tin_s)
                return v;
    }
    return c[0];
}

Subtask #1

0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	1 ms	512 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #2

0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	2 ms	640 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #3

16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	573 ms	792 KB	Output is correct
2	Correct	584 ms	1016 KB	Output is correct
3	Correct	969 ms	768 KB	Output is correct
4	Correct	839 ms	876 KB	Output is correct
5	Correct	642 ms	872 KB	Output is correct
6	Correct	474 ms	768 KB	Output is correct
7	Correct	459 ms	768 KB	Output is correct
8	Correct	2 ms	880 KB	Output is correct
9	Correct	6 ms	768 KB	Output is correct
10	Correct	2 ms	768 KB	Output is correct
11	Correct	616 ms	768 KB	Output is correct
12	Correct	490 ms	776 KB	Output is correct
13	Correct	479 ms	888 KB	Output is correct
14	Correct	468 ms	768 KB	Output is correct
15	Correct	73 ms	872 KB	Output is correct
16	Correct	92 ms	768 KB	Output is correct
17	Correct	152 ms	812 KB	Output is correct

Subtask #4

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	927 ms	768 KB	Output is correct
2	Correct	708 ms	880 KB	Output is correct
3	Correct	624 ms	1048 KB	Output is correct
4	Correct	2 ms	768 KB	Output is correct
5	Correct	5 ms	768 KB	Output is correct
6	Correct	2 ms	868 KB	Output is correct
7	Correct	596 ms	880 KB	Output is correct
8	Correct	1007 ms	768 KB	Output is correct
9	Correct	767 ms	768 KB	Output is correct
10	Correct	761 ms	768 KB	Output is correct
11	Correct	7 ms	872 KB	Output is correct
12	Correct	7 ms	768 KB	Output is correct
13	Correct	6 ms	876 KB	Output is correct
14	Correct	5 ms	1024 KB	Output is correct
15	Correct	1 ms	1132 KB	Output is correct
16	Correct	496 ms	1024 KB	Output is correct
17	Correct	573 ms	872 KB	Output is correct
18	Correct	662 ms	768 KB	Output is correct
19	Correct	564 ms	880 KB	Output is correct
20	Correct	621 ms	780 KB	Output is correct

Subtask #5

26.3205 / 61.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	548 ms	768 KB	Partially correct
2	Partially correct	449 ms	792 KB	Partially correct
3	Partially correct	990 ms	1040 KB	Partially correct
4	Partially correct	665 ms	876 KB	Partially correct
5	Partially correct	597 ms	876 KB	Partially correct
6	Partially correct	467 ms	768 KB	Partially correct
7	Partially correct	454 ms	768 KB	Partially correct
8	Partially correct	3 ms	768 KB	Partially correct
9	Partially correct	4 ms	888 KB	Partially correct
10	Partially correct	1 ms	876 KB	Partially correct
11	Partially correct	565 ms	768 KB	Partially correct
12	Partially correct	544 ms	824 KB	Partially correct
13	Partially correct	992 ms	868 KB	Partially correct
14	Partially correct	716 ms	768 KB	Partially correct
15	Partially correct	576 ms	768 KB	Partially correct
16	Partially correct	469 ms	828 KB	Partially correct
17	Partially correct	618 ms	768 KB	Partially correct
18	Partially correct	461 ms	908 KB	Partially correct
19	Partially correct	509 ms	768 KB	Partially correct
20	Partially correct	469 ms	824 KB	Partially correct
21	Partially correct	71 ms	868 KB	Partially correct
22	Partially correct	68 ms	768 KB	Partially correct
23	Partially correct	108 ms	768 KB	Partially correct
24	Partially correct	7 ms	880 KB	Partially correct
25	Partially correct	5 ms	888 KB	Partially correct
26	Partially correct	4 ms	876 KB	Partially correct
27	Partially correct	3 ms	768 KB	Partially correct
28	Partially correct	1 ms	876 KB	Partially correct
29	Partially correct	496 ms	768 KB	Partially correct
30	Partially correct	521 ms	768 KB	Partially correct
31	Partially correct	493 ms	872 KB	Partially correct
32	Partially correct	503 ms	1024 KB	Partially correct
33	Partially correct	503 ms	872 KB	Partially correct
34	Partially correct	345 ms	784 KB	Partially correct
35	Partially correct	449 ms	1024 KB	Partially correct
36	Partially correct	459 ms	996 KB	Partially correct
37	Partially correct	485 ms	784 KB	Partially correct
38	Partially correct	476 ms	908 KB	Partially correct
39	Partially correct	474 ms	768 KB	Partially correct
40	Partially correct	435 ms	776 KB	Partially correct
41	Partially correct	459 ms	912 KB	Partially correct
42	Partially correct	62 ms	828 KB	Partially correct
43	Partially correct	104 ms	816 KB	Partially correct
44	Partially correct	125 ms	788 KB	Partially correct
45	Partially correct	163 ms	800 KB	Partially correct
46	Partially correct	313 ms	828 KB	Partially correct
47	Partially correct	334 ms	796 KB	Partially correct
48	Partially correct	72 ms	768 KB	Partially correct
49	Partially correct	66 ms	1024 KB	Partially correct