oj.uz

Submission #679683

# Submission time Handle Problem Language Result Execution time Memory
679683 2023-01-09T00:37:52 Z phoebe Stations (IOI20_stations) C++17
100 / 100
 892 ms 800 KB 
#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
 
const int maxn = 1e3 + 10;
int n, sz[maxn] = {0}, h[maxn], x[maxn] = {0}; // even = mn, odd = mx
vector<int> adj[maxn];
 
void dfs1(int v, int p, int height){
    h[v] = height; sz[v] = 1; 
    for (auto u : adj[v]){
        if (u == p) continue;
        dfs1(u, v, height + 1);
        sz[v] += sz[u];
    }
}
 
void dfs2(int v, int p, int l, int r){
    if (h[v] % 2) x[v] = r--; // mx
    else x[v] = l++; // mn
    for (auto u : adj[v]){
        if (u == p) continue;
        dfs2(u, v, l, l + sz[u] - 1);
        l += sz[u];
    }
}
 
vector<int> label(int n, int k, vector<int> u, vector<int> v){
    // vector<int> BRUH(n); iota(BRUH.begin(), BRUH.end(), 0);
    for (auto &kjsgfh : adj) kjsgfh.clear();
    for (int i = 0; i < n - 1; i++){
        adj[u[i]].push_back(v[i]);
        adj[v[i]].push_back(u[i]);
    }
    // cout << endl;
    // for (int i = 0; i < n; i++){
    //     cout << i << ": ";
    //     for (auto u : adj[i]) cout << u << ' ';
    //     cout << endl;
    // }
    dfs1(0, 0, 0);
    // return BRUH;
    dfs2(0, 0, 0, n - 1);
    vector<int> re(n);
    for (int i = 0; i < n; i++) re[i] = x[i];
    // cout << endl;
    // for (int i = 0; i < n; i++) cout << x[i] << ' '; cout << endl;
    // for (int i = 0; i < n; i++) cout << h[i] << ' '; cout << endl;
    return re;
}
 
int find_next_station(int s, int t, vector<int> c){
    // return c[0];
    if (c.size() == 1) return c.front();
    if (s < c[0]){ // x[s] is min, root
        if (t < s || t > c[c.size() - 2]){ // not its children, go up
            return c.back();
        }
        else{ // else, go down, looking for smallest element in c >= t
            int idx = lower_bound(c.begin(), c.end(), t) - c.begin();
            return c[idx];
        }
    }
    else{ // x[s] is max
        if (t > s || t < c[1]) return c.front();
        else{
            int idx = upper_bound(c.begin(), c.end(), t) - c.begin();
            return c[idx - 1];
        }
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 517 ms 668 KB Output is correct
2 Correct 410 ms 672 KB Output is correct
3 Correct 849 ms 548 KB Output is correct
4 Correct 623 ms 420 KB Output is correct
5 Correct 595 ms 512 KB Output is correct
6 Correct 417 ms 544 KB Output is correct
7 Correct 433 ms 544 KB Output is correct
8 Correct 1 ms 628 KB Output is correct
9 Correct 3 ms 500 KB Output is correct
10 Correct 0 ms 628 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 389 ms 596 KB Output is correct
2 Correct 522 ms 548 KB Output is correct
3 Correct 816 ms 548 KB Output is correct
4 Correct 594 ms 548 KB Output is correct
5 Correct 495 ms 560 KB Output is correct
6 Correct 450 ms 532 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 546 ms 708 KB Output is correct
2 Correct 334 ms 672 KB Output is correct
3 Correct 850 ms 516 KB Output is correct
4 Correct 591 ms 528 KB Output is correct
5 Correct 545 ms 532 KB Output is correct
6 Correct 417 ms 648 KB Output is correct
7 Correct 484 ms 524 KB Output is correct
8 Correct 1 ms 620 KB Output is correct
9 Correct 4 ms 628 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 532 ms 532 KB Output is correct
12 Correct 367 ms 784 KB Output is correct
13 Correct 488 ms 676 KB Output is correct
14 Correct 388 ms 548 KB Output is correct
15 Correct 54 ms 576 KB Output is correct
16 Correct 41 ms 704 KB Output is correct
17 Correct 99 ms 656 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 891 ms 508 KB Output is correct
2 Correct 690 ms 528 KB Output is correct
3 Correct 524 ms 544 KB Output is correct
4 Correct 1 ms 500 KB Output is correct
5 Correct 4 ms 624 KB Output is correct
6 Correct 1 ms 628 KB Output is correct
7 Correct 547 ms 520 KB Output is correct
8 Correct 892 ms 420 KB Output is correct
9 Correct 674 ms 520 KB Output is correct
10 Correct 524 ms 520 KB Output is correct
11 Correct 4 ms 492 KB Output is correct
12 Correct 5 ms 628 KB Output is correct
13 Correct 4 ms 620 KB Output is correct
14 Correct 4 ms 628 KB Output is correct
15 Correct 1 ms 632 KB Output is correct
16 Correct 486 ms 416 KB Output is correct
17 Correct 502 ms 536 KB Output is correct
18 Correct 517 ms 420 KB Output is correct
19 Correct 440 ms 532 KB Output is correct
20 Correct 461 ms 544 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 509 ms 660 KB Output is correct
2 Correct 396 ms 648 KB Output is correct
3 Correct 819 ms 520 KB Output is correct
4 Correct 664 ms 544 KB Output is correct
5 Correct 516 ms 516 KB Output is correct
6 Correct 453 ms 672 KB Output is correct
7 Correct 429 ms 548 KB Output is correct
8 Correct 2 ms 620 KB Output is correct
9 Correct 4 ms 492 KB Output is correct
10 Correct 1 ms 624 KB Output is correct
11 Correct 313 ms 532 KB Output is correct
12 Correct 522 ms 536 KB Output is correct
13 Correct 867 ms 524 KB Output is correct
14 Correct 663 ms 504 KB Output is correct
15 Correct 519 ms 520 KB Output is correct
16 Correct 426 ms 532 KB Output is correct
17 Correct 508 ms 532 KB Output is correct
18 Correct 429 ms 656 KB Output is correct
19 Correct 482 ms 652 KB Output is correct
20 Correct 431 ms 548 KB Output is correct
21 Correct 59 ms 572 KB Output is correct
22 Correct 71 ms 544 KB Output is correct
23 Correct 96 ms 572 KB Output is correct
24 Correct 6 ms 492 KB Output is correct
25 Correct 4 ms 628 KB Output is correct
26 Correct 3 ms 632 KB Output is correct
27 Correct 3 ms 604 KB Output is correct
28 Correct 1 ms 628 KB Output is correct
29 Correct 495 ms 528 KB Output is correct
30 Correct 528 ms 528 KB Output is correct
31 Correct 506 ms 548 KB Output is correct
32 Correct 498 ms 548 KB Output is correct
33 Correct 443 ms 544 KB Output is correct
34 Correct 304 ms 544 KB Output is correct
35 Correct 401 ms 672 KB Output is correct
36 Correct 398 ms 748 KB Output is correct
37 Correct 429 ms 640 KB Output is correct
38 Correct 466 ms 524 KB Output is correct
39 Correct 412 ms 640 KB Output is correct
40 Correct 454 ms 648 KB Output is correct
41 Correct 425 ms 624 KB Output is correct
42 Correct 59 ms 600 KB Output is correct
43 Correct 93 ms 548 KB Output is correct
44 Correct 111 ms 544 KB Output is correct
45 Correct 142 ms 544 KB Output is correct
46 Correct 262 ms 532 KB Output is correct
47 Correct 278 ms 548 KB Output is correct
48 Correct 58 ms 788 KB Output is correct
49 Correct 57 ms 800 KB Output is correct