oj.uz

Submission #611477

# Submission time Handle Problem Language Result Execution time Memory
611477 2022-07-29T05:14:33 Z jophyyjh Stations (IOI20_stations) C++14
100 / 100
 1150 ms 752 KB 
/**
 * Not too difficult? From the scoring section, there exists a solution with K <= n
 * no matter what the tree looks like. Root the tree arbitrarily, we know that a path
 * in tree is the concat. of a path going upwards, reaching a "highest" node (LCA),
 * then going downwards. Therefore, a node shall determine if it should send a packet
 * to the parent or a certain child.
 * 
 * I guessed that the labelling has sth to do with subtree size. So maybe we can
 * assign n to the root, meaning that the subtree rooted at it has size = n. Hmm,
 * suppose that the root has 2 children, one of them has subtree size = a, the other
 * has subtree size b (a+b+1=n). We can assign n-1 to a, meaning that nodes in the
 * subtree of a has label <= n-1 (so we know whether we should send it upwards or
 * downward), then assign n-1-b to the subtree with size b. But the problem is we
 * only know the upper bound, not the lower bound!
 * So, the idea is to do this in an alternating fashion based on our nodes' depth.
 * The root r would be assigned 0, meaning that all nodes in this subtree has
 * label >= 0. Suppose that a, b are the only children of r. We assign n-1 to a, repr.
 * that all nodes in the subtree of a has labels <= n-1.
 * In the routing procedure, we get all the neighbours of a node v. All neighbours
 * must be in a different state as v (lower bound / upper bound?).
 * 
 *  K size:  N
 * Implementation 1
*/

#include <bits/stdc++.h>
#include "stations.h"

typedef std::vector<int>	vec;


std::vector<vec> tree;
vec subtree;
vec labels;

void find_size(int k, int parent) {
    subtree[k] = 1;
    for (int child : tree[k]) {
        if (child == parent)
            continue;
        find_size(child, k);
        subtree[k] += subtree[child];
    }
}

// Recursively assign labels. All nodes in the subtree
// rooted at k should have labels in [a, b].
void assign(int k, int parent, int a, int b, bool lower) {
    assert(a <= b);
    if (lower)
        labels[k] = a++;
    else
        labels[k] = b--;
    for (int child : tree[k]) {
        if (child == parent)
            continue;
        assign(child, k, a, a + subtree[child] - 1, !lower);
        a += subtree[child];
    }
}

vec label(int n, int K, vec u, vec v) {
    tree.assign(n, vec());
    for (int i = 0; i < n - 1; i++) {
        tree[u[i]].push_back(v[i]);
        tree[v[i]].push_back(u[i]);
    }
    subtree.resize(n);
    find_size(0, -1);
    labels.resize(n);
    assign(0, -1, 0, n - 1, true);
    return labels;
}


int find_next_station(int s, int t, vec c) {
    std::sort(c.begin(), c.end());
    bool lower;
    for (int neighb : c) {
        if (neighb > s)
            lower = true;
        else
            lower = false;
    }
    int parent = -1;
    if (s != 0) {
        if (lower)
            parent = c.back();
        else
            parent = c.front();
    }

    if (!lower)
        std::reverse(c.begin(), c.end());
    for (int child : c) {
        if (child == parent)
            continue;
        int a = s, b = child;
        if (!lower)
            std::swap(a, b);
        if (a <= t && t <= b)
            return child;
    }
    assert(parent != -1);
    return parent;
}

Compilation message

stations.cpp: In function 'int find_next_station(int, int, vec)':
stations.cpp:99:9: warning: 'lower' may be used uninitialized in this function [-Wmaybe-uninitialized]
   99 |         if (!lower)
      |         ^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 445 ms 676 KB Output is correct
2 Correct 486 ms 628 KB Output is correct
3 Correct 887 ms 416 KB Output is correct
4 Correct 747 ms 416 KB Output is correct
5 Correct 728 ms 504 KB Output is correct
6 Correct 488 ms 544 KB Output is correct
7 Correct 524 ms 636 KB Output is correct
8 Correct 3 ms 492 KB Output is correct
9 Correct 6 ms 456 KB Output is correct
10 Correct 2 ms 492 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 490 ms 492 KB Output is correct
2 Correct 670 ms 504 KB Output is correct
3 Correct 1002 ms 508 KB Output is correct
4 Correct 732 ms 416 KB Output is correct
5 Correct 524 ms 492 KB Output is correct
6 Correct 494 ms 556 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 716 ms 668 KB Output is correct
2 Correct 365 ms 632 KB Output is correct
3 Correct 874 ms 592 KB Output is correct
4 Correct 720 ms 484 KB Output is correct
5 Correct 573 ms 508 KB Output is correct
6 Correct 393 ms 640 KB Output is correct
7 Correct 578 ms 544 KB Output is correct
8 Correct 3 ms 496 KB Output is correct
9 Correct 6 ms 492 KB Output is correct
10 Correct 2 ms 492 KB Output is correct
11 Correct 728 ms 416 KB Output is correct
12 Correct 568 ms 728 KB Output is correct
13 Correct 446 ms 716 KB Output is correct
14 Correct 417 ms 576 KB Output is correct
15 Correct 57 ms 444 KB Output is correct
16 Correct 67 ms 544 KB Output is correct
17 Correct 156 ms 508 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1150 ms 484 KB Output is correct
2 Correct 737 ms 504 KB Output is correct
3 Correct 494 ms 508 KB Output is correct
4 Correct 2 ms 440 KB Output is correct
5 Correct 4 ms 492 KB Output is correct
6 Correct 2 ms 492 KB Output is correct
7 Correct 754 ms 512 KB Output is correct
8 Correct 1025 ms 512 KB Output is correct
9 Correct 590 ms 420 KB Output is correct
10 Correct 633 ms 508 KB Output is correct
11 Correct 6 ms 492 KB Output is correct
12 Correct 5 ms 492 KB Output is correct
13 Correct 4 ms 488 KB Output is correct
14 Correct 3 ms 420 KB Output is correct
15 Correct 2 ms 492 KB Output is correct
16 Correct 577 ms 416 KB Output is correct
17 Correct 597 ms 420 KB Output is correct
18 Correct 548 ms 500 KB Output is correct
19 Correct 534 ms 504 KB Output is correct
20 Correct 473 ms 416 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 490 ms 676 KB Output is correct
2 Correct 418 ms 720 KB Output is correct
3 Correct 899 ms 416 KB Output is correct
4 Correct 603 ms 416 KB Output is correct
5 Correct 583 ms 416 KB Output is correct
6 Correct 416 ms 548 KB Output is correct
7 Correct 494 ms 508 KB Output is correct
8 Correct 3 ms 492 KB Output is correct
9 Correct 6 ms 492 KB Output is correct
10 Correct 0 ms 492 KB Output is correct
11 Correct 449 ms 636 KB Output is correct
12 Correct 583 ms 508 KB Output is correct
13 Correct 1067 ms 484 KB Output is correct
14 Correct 830 ms 420 KB Output is correct
15 Correct 658 ms 416 KB Output is correct
16 Correct 380 ms 512 KB Output is correct
17 Correct 655 ms 552 KB Output is correct
18 Correct 506 ms 628 KB Output is correct
19 Correct 432 ms 752 KB Output is correct
20 Correct 596 ms 544 KB Output is correct
21 Correct 55 ms 416 KB Output is correct
22 Correct 90 ms 544 KB Output is correct
23 Correct 99 ms 572 KB Output is correct
24 Correct 5 ms 492 KB Output is correct
25 Correct 4 ms 492 KB Output is correct
26 Correct 3 ms 492 KB Output is correct
27 Correct 3 ms 492 KB Output is correct
28 Correct 1 ms 492 KB Output is correct
29 Correct 559 ms 416 KB Output is correct
30 Correct 478 ms 484 KB Output is correct
31 Correct 599 ms 508 KB Output is correct
32 Correct 499 ms 504 KB Output is correct
33 Correct 729 ms 504 KB Output is correct
34 Correct 365 ms 676 KB Output is correct
35 Correct 516 ms 620 KB Output is correct
36 Correct 534 ms 688 KB Output is correct
37 Correct 582 ms 724 KB Output is correct
38 Correct 527 ms 704 KB Output is correct
39 Correct 456 ms 720 KB Output is correct
40 Correct 448 ms 632 KB Output is correct
41 Correct 433 ms 628 KB Output is correct
42 Correct 53 ms 548 KB Output is correct
43 Correct 90 ms 544 KB Output is correct
44 Correct 144 ms 652 KB Output is correct
45 Correct 183 ms 672 KB Output is correct
46 Correct 318 ms 504 KB Output is correct
47 Correct 290 ms 504 KB Output is correct
48 Correct 65 ms 676 KB Output is correct
49 Correct 43 ms 548 KB Output is correct