제출 #611477

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
611477		jophyyjh	기지국 (IOI20_stations)	C++14	100 / 100	1150 ms	752 KiB

stations

/**
 * 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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 5
• Subtask 2: 8 / 8
• Subtask 3: 16 / 16
• Subtask 4: 10 / 10
• Subtask 5: 61 / 61