Submission #379481

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
379481	2021-03-18T10:07:23 Z	rocks03	Stations (IOI20_stations)	C++14	52.3205 / 100	1069 ms	1224 KB

stations

//#pragma GCC target("avx2")
//#pragma GCC optimization("O3")
//#pragma GCC optimization("unroll-loops")
#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()
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define Re(i, a, b) for(int i = (a); i >= (b); i--)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MAXN = 1e3;
vector<vector<int>> g;

int timer;
void dfs(int v, int p, vector<int>& labels){
    int tin = timer++;
    for(int u : g[v]){
        if(u ^ p){
            dfs(u, v, labels);
        }
    }
    int tou = timer - 1;
    labels[v] = MAXN * tin + tou;
}

vector<int> label(int N, int K, vector<int> u, vector<int> v){
    g.resize(N);
    rep(i, 0, N){
        g[i].clear();
    }
    auto add_edge = [&](int a, int b){
        g[a].pb(b);
        g[b].pb(a);
    };
    rep(i, 0, N - 1){
        add_edge(u[i], v[i]);
    }
    vector<int> labels(N);
    timer = 0;
    dfs(0, -1, labels);
    return labels;
}

int find_next_station(int a, int b, vector<int> c){
    auto get_label = [&](int x){
        pii ans = {x / MAXN, x % MAXN};
        return ans;
    };
    auto ancestor = [&] (pii u, pii v){
        bool is = (u.ff <= v.ff && v.ss <= u.ss);
        return is;
    };
    pii s = get_label(a), t = get_label(b);
    int parent;
    for(int x : c){
        pii u = get_label(x);
        if(ancestor(s, u)){
            if(ancestor(u, t))
                return x;
        } else{
            parent = x;
        }
    }
    return parent;
}

Compilation message

stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:61:9: warning: 'parent' may be used uninitialized in this function [-Wmaybe-uninitialized]
   61 |     int parent;
      |         ^~~~~~

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=6009
2	Halted	0 ms	0 KB	-

Subtask #2

0 / 8.0

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

Subtask #3

16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	609 ms	884 KB	Output is correct
2	Correct	514 ms	940 KB	Output is correct
3	Correct	1002 ms	864 KB	Output is correct
4	Correct	667 ms	1012 KB	Output is correct
5	Correct	736 ms	864 KB	Output is correct
6	Correct	499 ms	864 KB	Output is correct
7	Correct	535 ms	884 KB	Output is correct
8	Correct	3 ms	856 KB	Output is correct
9	Correct	5 ms	736 KB	Output is correct
10	Correct	2 ms	756 KB	Output is correct
11	Correct	629 ms	872 KB	Output is correct
12	Correct	475 ms	980 KB	Output is correct
13	Correct	448 ms	972 KB	Output is correct
14	Correct	506 ms	736 KB	Output is correct
15	Correct	62 ms	864 KB	Output is correct
16	Correct	79 ms	812 KB	Output is correct
17	Correct	113 ms	864 KB	Output is correct

Subtask #4

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	924 ms	768 KB	Output is correct
2	Correct	780 ms	756 KB	Output is correct
3	Correct	741 ms	1000 KB	Output is correct
4	Correct	3 ms	864 KB	Output is correct
5	Correct	4 ms	736 KB	Output is correct
6	Correct	2 ms	864 KB	Output is correct
7	Correct	700 ms	832 KB	Output is correct
8	Correct	1041 ms	864 KB	Output is correct
9	Correct	669 ms	864 KB	Output is correct
10	Correct	757 ms	864 KB	Output is correct
11	Correct	7 ms	756 KB	Output is correct
12	Correct	7 ms	736 KB	Output is correct
13	Correct	7 ms	864 KB	Output is correct
14	Correct	5 ms	896 KB	Output is correct
15	Correct	2 ms	756 KB	Output is correct
16	Correct	546 ms	736 KB	Output is correct
17	Correct	613 ms	844 KB	Output is correct
18	Correct	510 ms	864 KB	Output is correct
19	Correct	545 ms	736 KB	Output is correct
20	Correct	515 ms	872 KB	Output is correct

Subtask #5

26.3205 / 61.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	583 ms	940 KB	Partially correct
2	Partially correct	555 ms	1076 KB	Partially correct
3	Partially correct	976 ms	864 KB	Partially correct
4	Partially correct	770 ms	864 KB	Partially correct
5	Partially correct	775 ms	736 KB	Partially correct
6	Partially correct	571 ms	968 KB	Partially correct
7	Partially correct	489 ms	1008 KB	Partially correct
8	Partially correct	3 ms	736 KB	Partially correct
9	Partially correct	7 ms	756 KB	Partially correct
10	Partially correct	2 ms	756 KB	Partially correct
11	Partially correct	459 ms	888 KB	Partially correct
12	Partially correct	535 ms	736 KB	Partially correct
13	Partially correct	1069 ms	864 KB	Partially correct
14	Partially correct	800 ms	756 KB	Partially correct
15	Partially correct	772 ms	864 KB	Partially correct
16	Partially correct	533 ms	736 KB	Partially correct
17	Partially correct	685 ms	864 KB	Partially correct
18	Partially correct	496 ms	1120 KB	Partially correct
19	Partially correct	502 ms	968 KB	Partially correct
20	Partially correct	467 ms	768 KB	Partially correct
21	Partially correct	72 ms	756 KB	Partially correct
22	Partially correct	95 ms	756 KB	Partially correct
23	Partially correct	106 ms	756 KB	Partially correct
24	Partially correct	5 ms	864 KB	Partially correct
25	Partially correct	7 ms	796 KB	Partially correct
26	Partially correct	5 ms	776 KB	Partially correct
27	Partially correct	4 ms	736 KB	Partially correct
28	Partially correct	2 ms	680 KB	Partially correct
29	Partially correct	650 ms	736 KB	Partially correct
30	Partially correct	570 ms	864 KB	Partially correct
31	Partially correct	521 ms	736 KB	Partially correct
32	Partially correct	517 ms	992 KB	Partially correct
33	Partially correct	486 ms	756 KB	Partially correct
34	Partially correct	309 ms	884 KB	Partially correct
35	Partially correct	426 ms	956 KB	Partially correct
36	Partially correct	422 ms	952 KB	Partially correct
37	Partially correct	451 ms	884 KB	Partially correct
38	Partially correct	484 ms	864 KB	Partially correct
39	Partially correct	496 ms	1096 KB	Partially correct
40	Partially correct	536 ms	1224 KB	Partially correct
41	Partially correct	549 ms	1112 KB	Partially correct
42	Partially correct	80 ms	800 KB	Partially correct
43	Partially correct	140 ms	736 KB	Partially correct
44	Partially correct	157 ms	756 KB	Partially correct
45	Partially correct	172 ms	736 KB	Partially correct
46	Partially correct	298 ms	784 KB	Partially correct
47	Partially correct	339 ms	1008 KB	Partially correct
48	Partially correct	80 ms	992 KB	Partially correct
49	Partially correct	60 ms	1088 KB	Partially correct