제출 #1168359

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1168359		woohyun_jng	기지국 (IOI20_stations)	C++20	컴파일 에러	0 ms	0 KiB

stations

#include <bits/stdc++.h>
using namespace std;

typedef array<int, 2> pr;

const int MAX = 1001;

vector<int> adj[MAX];
int in[MAX], out[MAX], cnt;

void dfs(int node, int par) {
    in[node] = cnt++;
    for (int i : adj[node]) {
        if (i == par)
            continue;
        dfs(i, node);
    }
    out[node] = cnt - 1;
}

vector<int> label(int N, int K, vector<int> U, vector<int> V) {
    vector<int> labels(N);

    for (int i = 0; i < N - 1; i++)
        adj[U[i]].push_back(V[i]), adj[V[i]].push_back(U[i]);

    cnt = 0, dfs(0, -1);

    for (int i = 0; i < N; i++)
        labels[i] = in[i] * 1000 + out[i];

    return labels;
}

int find_next_station(int s, int t, vector<int> c) {
    int X, Y;

    pr S, T;
    vector<pr> C;

    S = {s / 1000, s % 1000}, T = {t / 1000, t % 1000};
    for (int i = 0; i < c.size(); i++) {
        X = c[i] / 1000, Y = c[i] % 1000;
        if (X <= S[0] && S[1] <= Y)
            continue;
        C.push_back({X, Y});
    };

    if (S[0] <= T[0] && T[0] <= S[1]) {
        for (pr i : C) {
            if (i[0] <= T[0] && T[1] <= i[1])
                return i[0] * 1000 + i[1];
        }
    } else
        return X * 1000 + Y;
}

static int max_label = 0;
static int r, n, k, q;
static std::vector<int> u, v, labels, answers;
static std::map<int, int> reverse_labels;
static std::vector<std::vector<int>> adjlist;
static int s, t, w;
static std::vector<int> c;

int main() {
    assert(scanf("%d", &r) == 1);
    for (int tc = 0; tc < r; tc++) {
        assert(scanf("%d%d", &n, &k) == 2);
        u.resize(n - 1);
        v.resize(n - 1);
        adjlist.clear();
        adjlist.resize(n);
        for (int i = 0; i < n - 1; i++) {
            assert(scanf("%d%d", &u[i], &v[i]) == 2);
            adjlist[u[i]].push_back(v[i]);
            adjlist[v[i]].push_back(u[i]);
        }
        labels = label(n, k, u, v);
        if ((int)labels.size() != n) {
            printf("Number of labels not equal to %d\n", n);
            exit(0);
        }
        reverse_labels.clear();
        for (int i = 0; i < n; i++) {
            if (labels[i] < 0 || labels[i] > k) {
                printf("Label not in range 0 to %d\n", k);
                exit(0);
            }
            if (reverse_labels.find(labels[i]) != reverse_labels.end()) {
                printf("Labels not unique\n");
                exit(0);
            }
            reverse_labels[labels[i]] = i;
            if (labels[i] > max_label) {
                max_label = labels[i];
            }
        }
        assert(scanf("%d", &q) == 1);
        for (int i = 0; i < q; i++) {
            assert(scanf("%d%d%d", &s, &t, &w) == 3);
            c.clear();
            for (int v : adjlist[s]) {
                c.push_back(labels[v]);
            }
            std::sort(c.begin(), c.end());
            int answer = find_next_station(labels[s], labels[t], c);
            if (!std::binary_search(c.begin(), c.end(), answer)) {
                printf("Label %d returned by find_next_station not found in c\n", answer);
                exit(0);
            }
            answers.push_back(reverse_labels[answer]);
        }
    }
    printf("%d\n", max_label);
    for (int index : answers) {
        printf("%d\n", index);
    }
    exit(0);
}

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

stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:57:1: warning: control reaches end of non-void function [-Wreturn-type]
   57 | }
      | ^
/usr/bin/ld: /tmp/ccZyv8sg.o: in function `main':
stub.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc5BQvWv.o:stations.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status