oj.uz

Submission #401666

# Submission time Handle Problem Language Result Execution time Memory
401666 2021-05-10T16:26:35 Z dxz05 Stations (IOI20_stations) C++14
100 / 100
 1140 ms 816 KB 
#include "stations.h"
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1011;

vector<int> g[MAXN];

int ID[MAXN], tin[MAXN], tout[MAXN], timer = 0;
void dfs(int v, int p, int dep){
    tin[v] = timer++;
    for (int u : g[v]){
        if (u != p) dfs(u, v, dep + 1);
    }
    tout[v] = timer++;
    ID[v] = (dep & 1 ? tin[v] : tout[v]);
}

bool line = true, binary = true;

vector<int> label(int n, int k, vector<int> U, vector<int> V) {
    for (int i = 0; i < n; i++) g[i].clear();
    timer = 0;

    for (int i = 0; i < n - 1; i++){
        g[U[i]].push_back(V[i]);
        g[V[i]].push_back(U[i]);
    }

    dfs(0, -1, 1);

	vector<int> labels(n, 0);
	for (int i = 0; i < n; i++){
        ID[i] /= 2;
        labels[i] = ID[i];
    }

	return labels;
}

int find_next_station(int s, int t, vector<int> c) {
    int sz = c.size();
    if (sz == 1) return c.back();

    if (c.front() > s){ // dep = odd
        int lf = s, rg = c[sz - 2];
        if (lf > t || rg < t) return c.back();

        int pos = lower_bound(c.begin(), c.end(), t) - c.begin();

        return c[pos];
    } else { // dep = even
        int lf = c[1], rg = s;
        if (lf > t || rg < t) return c.front();

        int pos = upper_bound(c.begin(), c.end(), t) - c.begin() - 1;

        return c[pos];
    }

    return c[0];
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 728 ms 644 KB Output is correct
2 Correct 582 ms 656 KB Output is correct
3 Correct 1077 ms 400 KB Output is correct
4 Correct 861 ms 544 KB Output is correct
5 Correct 750 ms 528 KB Output is correct
6 Correct 461 ms 520 KB Output is correct
7 Correct 456 ms 528 KB Output is correct
8 Correct 3 ms 476 KB Output is correct
9 Correct 4 ms 580 KB Output is correct
10 Correct 2 ms 468 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 565 ms 528 KB Output is correct
2 Correct 723 ms 520 KB Output is correct
3 Correct 1140 ms 516 KB Output is correct
4 Correct 881 ms 528 KB Output is correct
5 Correct 696 ms 528 KB Output is correct
6 Correct 612 ms 528 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 657 ms 664 KB Output is correct
2 Correct 464 ms 648 KB Output is correct
3 Correct 1053 ms 504 KB Output is correct
4 Correct 875 ms 400 KB Output is correct
5 Correct 733 ms 528 KB Output is correct
6 Correct 450 ms 508 KB Output is correct
7 Correct 437 ms 528 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 3 ms 604 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 723 ms 528 KB Output is correct
12 Correct 651 ms 656 KB Output is correct
13 Correct 482 ms 528 KB Output is correct
14 Correct 584 ms 528 KB Output is correct
15 Correct 53 ms 596 KB Output is correct
16 Correct 62 ms 580 KB Output is correct
17 Correct 107 ms 528 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 987 ms 416 KB Output is correct
2 Correct 800 ms 400 KB Output is correct
3 Correct 648 ms 528 KB Output is correct
4 Correct 3 ms 604 KB Output is correct
5 Correct 5 ms 596 KB Output is correct
6 Correct 2 ms 608 KB Output is correct
7 Correct 592 ms 400 KB Output is correct
8 Correct 890 ms 584 KB Output is correct
9 Correct 812 ms 400 KB Output is correct
10 Correct 867 ms 516 KB Output is correct
11 Correct 6 ms 596 KB Output is correct
12 Correct 8 ms 468 KB Output is correct
13 Correct 5 ms 448 KB Output is correct
14 Correct 3 ms 464 KB Output is correct
15 Correct 2 ms 464 KB Output is correct
16 Correct 520 ms 528 KB Output is correct
17 Correct 527 ms 520 KB Output is correct
18 Correct 581 ms 512 KB Output is correct
19 Correct 593 ms 540 KB Output is correct
20 Correct 587 ms 512 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 731 ms 632 KB Output is correct
2 Correct 492 ms 648 KB Output is correct
3 Correct 1021 ms 504 KB Output is correct
4 Correct 800 ms 520 KB Output is correct
5 Correct 655 ms 528 KB Output is correct
6 Correct 577 ms 656 KB Output is correct
7 Correct 493 ms 528 KB Output is correct
8 Correct 3 ms 596 KB Output is correct
9 Correct 6 ms 596 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 491 ms 520 KB Output is correct
12 Correct 678 ms 528 KB Output is correct
13 Correct 934 ms 400 KB Output is correct
14 Correct 743 ms 400 KB Output is correct
15 Correct 560 ms 516 KB Output is correct
16 Correct 532 ms 516 KB Output is correct
17 Correct 671 ms 512 KB Output is correct
18 Correct 546 ms 596 KB Output is correct
19 Correct 619 ms 744 KB Output is correct
20 Correct 511 ms 508 KB Output is correct
21 Correct 74 ms 548 KB Output is correct
22 Correct 73 ms 704 KB Output is correct
23 Correct 127 ms 640 KB Output is correct
24 Correct 7 ms 604 KB Output is correct
25 Correct 6 ms 596 KB Output is correct
26 Correct 6 ms 604 KB Output is correct
27 Correct 5 ms 476 KB Output is correct
28 Correct 2 ms 596 KB Output is correct
29 Correct 581 ms 528 KB Output is correct
30 Correct 597 ms 516 KB Output is correct
31 Correct 627 ms 528 KB Output is correct
32 Correct 593 ms 516 KB Output is correct
33 Correct 714 ms 528 KB Output is correct
34 Correct 411 ms 512 KB Output is correct
35 Correct 523 ms 760 KB Output is correct
36 Correct 605 ms 772 KB Output is correct
37 Correct 549 ms 764 KB Output is correct
38 Correct 536 ms 648 KB Output is correct
39 Correct 587 ms 756 KB Output is correct
40 Correct 480 ms 648 KB Output is correct
41 Correct 580 ms 816 KB Output is correct
42 Correct 67 ms 520 KB Output is correct
43 Correct 146 ms 676 KB Output is correct
44 Correct 189 ms 544 KB Output is correct
45 Correct 182 ms 608 KB Output is correct
46 Correct 374 ms 512 KB Output is correct
47 Correct 287 ms 512 KB Output is correct
48 Correct 74 ms 676 KB Output is correct
49 Correct 78 ms 676 KB Output is correct