oj.uz

Submission #401664

# Submission time Handle Problem Language Result Execution time Memory
401664 2021-05-10T16:21:48 Z dxz05 Stations (IOI20_stations) C++14
76 / 100
 1115 ms 836 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++){
        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
0 / 5.0

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

Subtask #2
0 / 8.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 527 ms 780 KB Output is correct
2 Correct 551 ms 644 KB Output is correct
3 Correct 937 ms 720 KB Output is correct
4 Correct 794 ms 528 KB Output is correct
5 Correct 694 ms 528 KB Output is correct
6 Correct 604 ms 640 KB Output is correct
7 Correct 610 ms 528 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 5 ms 596 KB Output is correct
10 Correct 2 ms 600 KB Output is correct
11 Correct 697 ms 516 KB Output is correct
12 Correct 481 ms 652 KB Output is correct
13 Correct 539 ms 632 KB Output is correct
14 Correct 500 ms 656 KB Output is correct
15 Correct 67 ms 576 KB Output is correct
16 Correct 93 ms 528 KB Output is correct
17 Correct 117 ms 528 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 943 ms 492 KB Output is correct
2 Correct 753 ms 400 KB Output is correct
3 Correct 781 ms 400 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 5 ms 596 KB Output is correct
6 Correct 2 ms 464 KB Output is correct
7 Correct 693 ms 656 KB Output is correct
8 Correct 1007 ms 636 KB Output is correct
9 Correct 778 ms 400 KB Output is correct
10 Correct 663 ms 548 KB Output is correct
11 Correct 5 ms 596 KB Output is correct
12 Correct 7 ms 596 KB Output is correct
13 Correct 6 ms 608 KB Output is correct
14 Correct 4 ms 468 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 625 ms 536 KB Output is correct
17 Correct 576 ms 528 KB Output is correct
18 Correct 663 ms 512 KB Output is correct
19 Correct 639 ms 528 KB Output is correct
20 Correct 490 ms 516 KB Output is correct

Subtask #5
50.0 / 61.0

# Verdict Execution time Memory Grader output
1 Partially correct 712 ms 660 KB Partially correct
2 Partially correct 637 ms 616 KB Partially correct
3 Correct 1115 ms 560 KB Output is correct
4 Correct 757 ms 512 KB Output is correct
5 Correct 566 ms 516 KB Output is correct
6 Partially correct 492 ms 656 KB Partially correct
7 Partially correct 475 ms 504 KB Partially correct
8 Correct 3 ms 596 KB Output is correct
9 Correct 4 ms 468 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Partially correct 510 ms 504 KB Partially correct
12 Partially correct 672 ms 528 KB Partially correct
13 Correct 1059 ms 520 KB Output is correct
14 Correct 819 ms 516 KB Output is correct
15 Correct 683 ms 512 KB Output is correct
16 Partially correct 531 ms 496 KB Partially correct
17 Correct 663 ms 556 KB Output is correct
18 Partially correct 603 ms 748 KB Partially correct
19 Partially correct 477 ms 776 KB Partially correct
20 Partially correct 570 ms 528 KB Partially correct
21 Correct 57 ms 596 KB Output is correct
22 Partially correct 69 ms 548 KB Partially correct
23 Partially correct 104 ms 528 KB Partially correct
24 Correct 7 ms 596 KB Output is correct
25 Correct 5 ms 596 KB Output is correct
26 Correct 5 ms 604 KB Output is correct
27 Correct 5 ms 596 KB Output is correct
28 Correct 2 ms 596 KB Output is correct
29 Correct 608 ms 512 KB Output is correct
30 Correct 567 ms 656 KB Output is correct
31 Correct 652 ms 528 KB Output is correct
32 Correct 624 ms 528 KB Output is correct
33 Correct 562 ms 656 KB Output is correct
34 Partially correct 320 ms 636 KB Partially correct
35 Partially correct 547 ms 636 KB Partially correct
36 Partially correct 442 ms 644 KB Partially correct
37 Partially correct 542 ms 568 KB Partially correct
38 Partially correct 516 ms 520 KB Partially correct
39 Partially correct 464 ms 748 KB Partially correct
40 Partially correct 542 ms 724 KB Partially correct
41 Partially correct 611 ms 764 KB Partially correct
42 Partially correct 65 ms 672 KB Partially correct
43 Partially correct 139 ms 784 KB Partially correct
44 Partially correct 177 ms 528 KB Partially correct
45 Partially correct 173 ms 528 KB Partially correct
46 Partially correct 349 ms 516 KB Partially correct
47 Partially correct 374 ms 528 KB Partially correct
48 Partially correct 62 ms 676 KB Partially correct
49 Partially correct 72 ms 836 KB Partially correct