oj.uz

Submission #321449

# Submission time Handle Problem Language Result Execution time Memory
321449 2020-11-12T11:20:05 Z grt Stations (IOI20_stations) C++17
100 / 100
 936 ms 1284 KB 
#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;
using ll = long long;
using pi = pair<int,int>;

#define ST first
#define ND second
#define PB push_back

const int nax = 1000 + 10;
vi V[nax];
bool visited[nax];
int cur;
int num[nax], dep[nax];

void dfs(int x) {
    visited[x] = 1;
    if(dep[x]%2==0) {
        num[x] = cur;
        cur++;
    }
    for(int nbh : V[x]) if(!visited[nbh]) {
        dep[nbh] = dep[x] + 1;
        dfs(nbh);
    }
    if(dep[x]%2==1) {
        num[x] = cur;
        cur++;
    }
}


vi label(int n, int k, vi u, vi v) {
    for(int i = 0; i < n; ++i) {
        visited[i] = 0;
        V[i].clear();
    }
    for(int i = 0; i < n - 1; ++i) {
        V[v[i]].PB(u[i]);
        V[u[i]].PB(v[i]);
    }
    cur = 0;
    dfs(0);
    vi ans(n);
    for(int i = 0; i < n; ++i) ans[i] = num[i];
    return ans;
}

int find_next_station(int s, int y, vi c) {
    if((int)c.size() == 1) return c.back();
    if(s < c[0]) {
        if(y < s || y > c[(int)c.size() - 2]) {
            return c.back();
        }
        int x = 0;
        while(c[x] < y) x++;
        return c[x];
    } else {
        if(y > s || y < c[1]) {
            return c[0];
        }
        int x = (int)c.size() - 1;
        while(y < c[x]) x--;
        return c[x];
    }
}
/*
int main() {
    vi res = label(5, 10, {0, 1, 1, 2}, {1, 2, 3, 4});
    for(int i = 0; i < 5; ++i) cout << res[i] << " ";
    cout << "\n";
    cout << find_next_station(1, 3, {2, 4}) << "\n";
}
*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 561 ms 864 KB Output is correct
2 Correct 540 ms 984 KB Output is correct
3 Correct 865 ms 864 KB Output is correct
4 Correct 696 ms 944 KB Output is correct
5 Correct 608 ms 864 KB Output is correct
6 Correct 537 ms 1108 KB Output is correct
7 Correct 473 ms 992 KB Output is correct
8 Correct 3 ms 864 KB Output is correct
9 Correct 4 ms 904 KB Output is correct
10 Correct 2 ms 736 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 501 ms 864 KB Output is correct
2 Correct 624 ms 864 KB Output is correct
3 Correct 886 ms 864 KB Output is correct
4 Correct 708 ms 864 KB Output is correct
5 Correct 563 ms 944 KB Output is correct
6 Correct 465 ms 992 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 633 ms 1100 KB Output is correct
2 Correct 478 ms 864 KB Output is correct
3 Correct 910 ms 1072 KB Output is correct
4 Correct 718 ms 944 KB Output is correct
5 Correct 617 ms 944 KB Output is correct
6 Correct 452 ms 1104 KB Output is correct
7 Correct 432 ms 864 KB Output is correct
8 Correct 3 ms 864 KB Output is correct
9 Correct 4 ms 736 KB Output is correct
10 Correct 2 ms 736 KB Output is correct
11 Correct 662 ms 944 KB Output is correct
12 Correct 522 ms 1248 KB Output is correct
13 Correct 551 ms 1284 KB Output is correct
14 Correct 454 ms 904 KB Output is correct
15 Correct 43 ms 936 KB Output is correct
16 Correct 75 ms 736 KB Output is correct
17 Correct 134 ms 864 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 834 ms 864 KB Output is correct
2 Correct 658 ms 864 KB Output is correct
3 Correct 748 ms 1072 KB Output is correct
4 Correct 3 ms 952 KB Output is correct
5 Correct 5 ms 864 KB Output is correct
6 Correct 1 ms 736 KB Output is correct
7 Correct 646 ms 884 KB Output is correct
8 Correct 936 ms 836 KB Output is correct
9 Correct 669 ms 864 KB Output is correct
10 Correct 592 ms 944 KB Output is correct
11 Correct 4 ms 736 KB Output is correct
12 Correct 6 ms 864 KB Output is correct
13 Correct 5 ms 736 KB Output is correct
14 Correct 4 ms 944 KB Output is correct
15 Correct 2 ms 944 KB Output is correct
16 Correct 518 ms 736 KB Output is correct
17 Correct 530 ms 944 KB Output is correct
18 Correct 578 ms 944 KB Output is correct
19 Correct 559 ms 1120 KB Output is correct
20 Correct 549 ms 864 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 605 ms 992 KB Output is correct
2 Correct 460 ms 864 KB Output is correct
3 Correct 851 ms 944 KB Output is correct
4 Correct 588 ms 1072 KB Output is correct
5 Correct 580 ms 944 KB Output is correct
6 Correct 432 ms 864 KB Output is correct
7 Correct 574 ms 736 KB Output is correct
8 Correct 3 ms 952 KB Output is correct
9 Correct 6 ms 864 KB Output is correct
10 Correct 2 ms 736 KB Output is correct
11 Correct 466 ms 736 KB Output is correct
12 Correct 525 ms 896 KB Output is correct
13 Correct 880 ms 1004 KB Output is correct
14 Correct 739 ms 864 KB Output is correct
15 Correct 580 ms 952 KB Output is correct
16 Correct 462 ms 864 KB Output is correct
17 Correct 639 ms 1072 KB Output is correct
18 Correct 494 ms 1244 KB Output is correct
19 Correct 507 ms 1100 KB Output is correct
20 Correct 451 ms 896 KB Output is correct
21 Correct 61 ms 736 KB Output is correct
22 Correct 72 ms 736 KB Output is correct
23 Correct 113 ms 900 KB Output is correct
24 Correct 7 ms 944 KB Output is correct
25 Correct 6 ms 952 KB Output is correct
26 Correct 6 ms 864 KB Output is correct
27 Correct 4 ms 952 KB Output is correct
28 Correct 1 ms 864 KB Output is correct
29 Correct 605 ms 736 KB Output is correct
30 Correct 488 ms 944 KB Output is correct
31 Correct 478 ms 952 KB Output is correct
32 Correct 716 ms 864 KB Output is correct
33 Correct 545 ms 864 KB Output is correct
34 Correct 326 ms 992 KB Output is correct
35 Correct 466 ms 1092 KB Output is correct
36 Correct 467 ms 992 KB Output is correct
37 Correct 435 ms 1120 KB Output is correct
38 Correct 489 ms 1108 KB Output is correct
39 Correct 461 ms 1072 KB Output is correct
40 Correct 472 ms 856 KB Output is correct
41 Correct 496 ms 1244 KB Output is correct
42 Correct 62 ms 864 KB Output is correct
43 Correct 131 ms 880 KB Output is correct
44 Correct 123 ms 864 KB Output is correct
45 Correct 213 ms 864 KB Output is correct
46 Correct 343 ms 896 KB Output is correct
47 Correct 416 ms 896 KB Output is correct
48 Correct 62 ms 1096 KB Output is correct
49 Correct 66 ms 864 KB Output is correct