oj.uz

Submission #305079

# Submission time Handle Problem Language Result Execution time Memory
305079 2020-09-22T14:23:19 Z MarcoMeijer Stations (IOI20_stations) C++14
100 / 100
 1160 ms 24832 KB 
#include "stations.h"
#include <bits/stdc++.h>

using namespace std;

#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define RE(a,b) REP(a,0,b)
#define FOR(a,b) for(auto& a:b)
#define pb push_back
#define fi first
#define se second
#define all(a) a.begin(), a.end()

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;

const int INF=1e9;
const int MX=5e5;

int  M;
vi adj[MX];
vi lab;

void dfs(int u, int p=-1, bool pre=1) {
    if( pre) lab[u] = M++;
    FOR(v,adj[u]) if(v!=p) dfs(v,u,!pre);
    if(!pre) lab[u] = M++;
}

vi label(int n, int k, vi U, vi V) {
    lab.assign(n,0);
    RE(i,n) adj[i].clear();
    RE(i,n-1) {
        adj[U[i]].pb(V[i]);
        adj[V[i]].pb(U[i]);
    }

    M=0;
    dfs(0);
    return lab;
}

int find_next_station(int s, int t, vi c) {
    if(c.size() == 1) return c[0];
    if(s < c[0]) {
        // s is pre
        if(s == 0) {
            // s is root
            FOR(i,c) if(i >= t) return i;
        } else {
            int par = c.back();
            if(t < s) return par;
            FOR(i,c) if(i != par && i >= t) return i;
            return par;
        }
    } else {
        // s is post
        int par = c[0];
        if(t > s) return par;
        REV(i,0,c.size()) if(c[i] != par && c[i] <= t) return c[i];
        return par;
    }
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 620 ms 24448 KB Output is correct
2 Correct 589 ms 24448 KB Output is correct
3 Correct 1019 ms 24268 KB Output is correct
4 Correct 862 ms 24264 KB Output is correct
5 Correct 632 ms 24200 KB Output is correct
6 Correct 601 ms 24440 KB Output is correct
7 Correct 584 ms 24312 KB Output is correct
8 Correct 19 ms 24192 KB Output is correct
9 Correct 23 ms 24064 KB Output is correct
10 Correct 18 ms 24320 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 489 ms 24416 KB Output is correct
2 Correct 665 ms 24548 KB Output is correct
3 Correct 1108 ms 24260 KB Output is correct
4 Correct 897 ms 24064 KB Output is correct
5 Correct 696 ms 24192 KB Output is correct
6 Correct 679 ms 24472 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 731 ms 24512 KB Output is correct
2 Correct 485 ms 24312 KB Output is correct
3 Correct 1102 ms 24396 KB Output is correct
4 Correct 797 ms 24304 KB Output is correct
5 Correct 666 ms 24192 KB Output is correct
6 Correct 538 ms 24332 KB Output is correct
7 Correct 561 ms 24332 KB Output is correct
8 Correct 18 ms 24192 KB Output is correct
9 Correct 23 ms 24192 KB Output is correct
10 Correct 19 ms 24200 KB Output is correct
11 Correct 725 ms 24392 KB Output is correct
12 Correct 662 ms 24364 KB Output is correct
13 Correct 548 ms 24440 KB Output is correct
14 Correct 563 ms 24360 KB Output is correct
15 Correct 86 ms 24192 KB Output is correct
16 Correct 107 ms 24352 KB Output is correct
17 Correct 163 ms 24320 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1160 ms 24412 KB Output is correct
2 Correct 757 ms 24320 KB Output is correct
3 Correct 807 ms 24064 KB Output is correct
4 Correct 20 ms 24328 KB Output is correct
5 Correct 19 ms 24212 KB Output is correct
6 Correct 20 ms 24328 KB Output is correct
7 Correct 818 ms 24192 KB Output is correct
8 Correct 1079 ms 24200 KB Output is correct
9 Correct 981 ms 24328 KB Output is correct
10 Correct 756 ms 24268 KB Output is correct
11 Correct 20 ms 24320 KB Output is correct
12 Correct 25 ms 24348 KB Output is correct
13 Correct 22 ms 24192 KB Output is correct
14 Correct 22 ms 24320 KB Output is correct
15 Correct 20 ms 24064 KB Output is correct
16 Correct 567 ms 24192 KB Output is correct
17 Correct 562 ms 24352 KB Output is correct
18 Correct 559 ms 24192 KB Output is correct
19 Correct 641 ms 24144 KB Output is correct
20 Correct 527 ms 24316 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 628 ms 24320 KB Output is correct
2 Correct 511 ms 24304 KB Output is correct
3 Correct 1038 ms 24200 KB Output is correct
4 Correct 787 ms 24344 KB Output is correct
5 Correct 799 ms 24200 KB Output is correct
6 Correct 597 ms 24440 KB Output is correct
7 Correct 689 ms 24184 KB Output is correct
8 Correct 19 ms 24192 KB Output is correct
9 Correct 20 ms 24064 KB Output is correct
10 Correct 19 ms 24192 KB Output is correct
11 Correct 563 ms 24328 KB Output is correct
12 Correct 739 ms 24224 KB Output is correct
13 Correct 1025 ms 24320 KB Output is correct
14 Correct 834 ms 24200 KB Output is correct
15 Correct 697 ms 24396 KB Output is correct
16 Correct 559 ms 24308 KB Output is correct
17 Correct 676 ms 24200 KB Output is correct
18 Correct 688 ms 24332 KB Output is correct
19 Correct 552 ms 24320 KB Output is correct
20 Correct 690 ms 24564 KB Output is correct
21 Correct 84 ms 24064 KB Output is correct
22 Correct 104 ms 24192 KB Output is correct
23 Correct 124 ms 24320 KB Output is correct
24 Correct 23 ms 24204 KB Output is correct
25 Correct 22 ms 24192 KB Output is correct
26 Correct 20 ms 24320 KB Output is correct
27 Correct 22 ms 24320 KB Output is correct
28 Correct 17 ms 24200 KB Output is correct
29 Correct 659 ms 24200 KB Output is correct
30 Correct 747 ms 24224 KB Output is correct
31 Correct 564 ms 24216 KB Output is correct
32 Correct 676 ms 24320 KB Output is correct
33 Correct 653 ms 24192 KB Output is correct
34 Correct 477 ms 24448 KB Output is correct
35 Correct 736 ms 24832 KB Output is correct
36 Correct 650 ms 24464 KB Output is correct
37 Correct 558 ms 24320 KB Output is correct
38 Correct 583 ms 24300 KB Output is correct
39 Correct 589 ms 24448 KB Output is correct
40 Correct 666 ms 24376 KB Output is correct
41 Correct 545 ms 24304 KB Output is correct
42 Correct 118 ms 24448 KB Output is correct
43 Correct 138 ms 24320 KB Output is correct
44 Correct 176 ms 24320 KB Output is correct
45 Correct 225 ms 24320 KB Output is correct
46 Correct 376 ms 24328 KB Output is correct
47 Correct 518 ms 24448 KB Output is correct
48 Correct 112 ms 24448 KB Output is correct
49 Correct 93 ms 24560 KB Output is correct