Submission #373672

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
373672	2021-03-05T11:46:36 Z	Jarif_Rahman	Stations (IOI20_stations)	C++17	52.3244 / 100	943 ms	1340 KB

stations

#include "stations.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
vector<vector<int>> v;
vector<int> lb, sz;
pair<int, int> div(int x){
    return make_pair(x/1000, x%1000 + 1);
}
int in = 0;
void dfs(int nd, int ss){
    lb[nd] = 1000*in;
    in++;
    for(int x: v[nd]) if(x!=ss) dfs(x, nd);
    for(int x: v[nd]) if(x!=ss) sz[nd]+=sz[x];
    lb[nd]+=sz[nd]-1;
}
vector<int> label(int n, int k, vector<int> aa, vector<int> bb){
    in = 0;
    v.assign(n, {});
    lb.assign(n, -1);
    sz.assign(n, 1);
    for(int i = 0; i < n-1; i++){
        v[aa[i]].pb(bb[i]);
        v[bb[i]].pb(aa[i]);
    }
    dfs(0, -1);
    return lb;
}
int find_next_station(int s, int t, vector<int> c){
    auto [a, b] = div(s);
    auto [x, y] = div(t);
    if(x < a || x > a+b-1){
        for(int xx: c){
            auto [aa, bb] = div(xx);
            if(aa < a) return xx;
        }
        exit(0);
    }
    for(int xx: c){
        auto [aa, bb] = div(xx);
        if(a >= aa && a <= aa+bb-1) continue;
        if(x >= aa && x <= aa+bb-1) return xx;
    }
}

Compilation message

stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:49:1: warning: control reaches end of non-void function [-Wreturn-type]
   49 | }
      | ^

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

Subtask #2

0 / 8.0

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

Subtask #3

16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	544 ms	892 KB	Output is correct
2	Correct	463 ms	1012 KB	Output is correct
3	Correct	897 ms	1188 KB	Output is correct
4	Correct	640 ms	868 KB	Output is correct
5	Correct	602 ms	756 KB	Output is correct
6	Correct	455 ms	984 KB	Output is correct
7	Correct	425 ms	884 KB	Output is correct
8	Correct	3 ms	868 KB	Output is correct
9	Correct	5 ms	884 KB	Output is correct
10	Correct	1 ms	876 KB	Output is correct
11	Correct	587 ms	1060 KB	Output is correct
12	Correct	463 ms	980 KB	Output is correct
13	Correct	483 ms	980 KB	Output is correct
14	Correct	447 ms	788 KB	Output is correct
15	Correct	62 ms	796 KB	Output is correct
16	Correct	65 ms	756 KB	Output is correct
17	Correct	120 ms	736 KB	Output is correct

Subtask #4

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	873 ms	868 KB	Output is correct
2	Correct	699 ms	756 KB	Output is correct
3	Correct	552 ms	884 KB	Output is correct
4	Correct	3 ms	736 KB	Output is correct
5	Correct	5 ms	776 KB	Output is correct
6	Correct	2 ms	996 KB	Output is correct
7	Correct	566 ms	756 KB	Output is correct
8	Correct	939 ms	868 KB	Output is correct
9	Correct	702 ms	868 KB	Output is correct
10	Correct	596 ms	868 KB	Output is correct
11	Correct	8 ms	756 KB	Output is correct
12	Correct	7 ms	796 KB	Output is correct
13	Correct	3 ms	756 KB	Output is correct
14	Correct	4 ms	868 KB	Output is correct
15	Correct	2 ms	868 KB	Output is correct
16	Correct	512 ms	868 KB	Output is correct
17	Correct	487 ms	868 KB	Output is correct
18	Correct	499 ms	884 KB	Output is correct
19	Correct	579 ms	884 KB	Output is correct
20	Correct	566 ms	868 KB	Output is correct

Subtask #5

26.3244 / 61.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	636 ms	1328 KB	Partially correct
2	Partially correct	492 ms	864 KB	Partially correct
3	Correct	943 ms	736 KB	Output is correct
4	Partially correct	677 ms	736 KB	Partially correct
5	Partially correct	585 ms	868 KB	Partially correct
6	Partially correct	509 ms	884 KB	Partially correct
7	Partially correct	448 ms	760 KB	Partially correct
8	Partially correct	3 ms	908 KB	Partially correct
9	Partially correct	5 ms	880 KB	Partially correct
10	Partially correct	2 ms	884 KB	Partially correct
11	Partially correct	474 ms	884 KB	Partially correct
12	Partially correct	597 ms	896 KB	Partially correct
13	Correct	884 ms	736 KB	Output is correct
14	Partially correct	662 ms	756 KB	Partially correct
15	Partially correct	597 ms	864 KB	Partially correct
16	Partially correct	441 ms	756 KB	Partially correct
17	Partially correct	645 ms	868 KB	Partially correct
18	Partially correct	487 ms	788 KB	Partially correct
19	Partially correct	503 ms	988 KB	Partially correct
20	Partially correct	442 ms	736 KB	Partially correct
21	Partially correct	67 ms	776 KB	Partially correct
22	Partially correct	64 ms	736 KB	Partially correct
23	Partially correct	108 ms	736 KB	Partially correct
24	Partially correct	6 ms	756 KB	Partially correct
25	Partially correct	6 ms	756 KB	Partially correct
26	Partially correct	5 ms	736 KB	Partially correct
27	Partially correct	4 ms	916 KB	Partially correct
28	Partially correct	2 ms	876 KB	Partially correct
29	Partially correct	542 ms	736 KB	Partially correct
30	Partially correct	501 ms	868 KB	Partially correct
31	Partially correct	482 ms	868 KB	Partially correct
32	Partially correct	485 ms	868 KB	Partially correct
33	Partially correct	535 ms	868 KB	Partially correct
34	Partially correct	307 ms	864 KB	Partially correct
35	Partially correct	442 ms	992 KB	Partially correct
36	Partially correct	514 ms	1340 KB	Partially correct
37	Partially correct	570 ms	1024 KB	Partially correct
38	Partially correct	503 ms	984 KB	Partially correct
39	Partially correct	459 ms	1040 KB	Partially correct
40	Partially correct	538 ms	984 KB	Partially correct
41	Partially correct	512 ms	988 KB	Partially correct
42	Partially correct	72 ms	952 KB	Partially correct
43	Partially correct	136 ms	736 KB	Partially correct
44	Partially correct	136 ms	756 KB	Partially correct
45	Partially correct	199 ms	884 KB	Partially correct
46	Partially correct	360 ms	756 KB	Partially correct
47	Partially correct	297 ms	1176 KB	Partially correct
48	Partially correct	64 ms	884 KB	Partially correct
49	Partially correct	63 ms	992 KB	Partially correct