Submission #1296339

#	Time	Username	Problem	Language	Result	Execution time	Memory
1296339		eri16	Stations (IOI20_stations)	C++20	Compilation error	0 ms	0 KiB

stations

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

vector<int> lbl;

// dfs with parent avoids revisiting and is safe for undirected tree
void dfs(int node, int parent, const vector<vector<int>>& adj, int &depth) {
    int in = depth++;
    for (int nb : adj[node]) {
        if (nb == parent) continue;
        dfs(nb, node, adj, depth);
    }
    int out = depth++;
    lbl[node] = in * 1000 + out; // ok for depth < 1000 as in problem statement
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
    // detect whether input appears 1-indexed (common). If so, convert to 0-based.
    bool one_indexed = false;
    for (int x : u) if (x == n) one_indexed = true;
    for (int x : v) if (x == n) one_indexed = true;
    if (one_indexed) {
        for (int &x : u) --x;
        for (int &x : v) --x;
    }

    lbl.assign(n, 0);
    vector<vector<int>> adj(n);            // use n, not n+1
    for (int i = 0; i < n - 1; ++i) {
        adj[u[i]].push_back(v[i]);
        adj[v[i]].push_back(u[i]);
    }

    int depth = 0;
    dfs(0, -1, adj, depth); // root at 0 (after conversion above)
    return lbl;
}

int find_next_station(int s_enc, int t_enc, const vector<int>& cp) {
    if (cp.empty()) return -1;

    int in_s = s_enc / 1000;
    int out_s = s_enc % 1000;
    int in_t = t_enc / 1000;
    int out_t = t_enc % 1000;

    // find deepest cp ancestor of s (max in)
    int parent_idx = -1;
    int best_in = -1;
    for (int i = 0; i < (int)cp.size(); ++i) {
        int k1 = cp[i] / 1000;
        int k2 = cp[i] % 1000;
        if (k1 <= in_s && out_s <= k2) {
            if (k1 > best_in) {
                best_in = k1;
                parent_idx = i;
            }
        }
    }
    if (parent_idx == -1) return -1; // no cp ancestor found -> cannot answer

    // find deepest cp ancestor of t that is deeper than parent (closer to t)
    int candidate = -1;
    int cand_in = -1;
    for (int i = 0; i < (int)cp.size(); ++i) {
        if (i == parent_idx) continue;           // skip parent
        int k1 = cp[i] / 1000;
        int k2 = cp[i] % 1000;
        if (k1 <= in_t && out_t <= k2) {         // cp[i] ancestor of t
            if (k1 > best_in && k1 > cand_in) {  // strictly deeper than parent
                cand_in = k1;
                candidate = i;
            }
        }
    }

    if (candidate != -1) return cp[candidate];
    return cp[parent_idx];
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccO3Q0Mf.o: in function `main':
stub.cpp:(.text.startup+0x4ce): undefined reference to `find_next_station(int, int, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status