Submission #1065791

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065791		vjudge1	Stations (IOI20_stations)	C++17	100 / 100	657 ms	1472 KiB

stations

#include "stations.h"

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

struct tree {
    int n;

    vi sz;
    vector<vi> L;

    tree(int N) : n(N), sz(N, 1), L(N) {}

    void add_edge(int u, int v) {
        L[u].push_back(v);
        L[v].push_back(u);
    }

    vi get_labels() {
        function<void(int, int)> dfs0 = [&](int u, int p) {
            sz[u] = 1;
            for(auto it : L[u]) {
                if(it == p) continue;
                dfs0(it, u);
                sz[u] += sz[it];
            }
        };
        dfs0(0, -1);

        vi Re(n, -1);

        function<void(int, int, int, int, int)> dfs = 
            [&](int u, int p, int l, int r, int tip) {
                if(tip) {
                    Re[u] = l;
                    int v = l + 1;
                    for(auto it : L[u]) {
                        if(it == p) continue;
                        dfs(it, u, v, v + sz[it] - 1, tip ^ 1);
                        v += sz[it];
                    }
                } else {
                    Re[u] = r;
                    int v = r - 1;
                    for(auto it : L[u]) {
                        if(it == p) continue;
                        dfs(it, u, v - sz[it] + 1, v, tip ^ 1);
                        v -= sz[it];
                    }
                }
        };
        dfs(0, -1, 0, n - 1, 0);
       // printf("Labels: ");
       // for(auto it : Re) printf("%d ", it);
       // printf("\n");

        return Re;
    }
};
vi label(int n, int k, vi u, vi v) {
    tree T(n);
    for(int i = 0; i + 1 < n; ++i)
        T.add_edge(u[i], v[i]);

    return T.get_labels();
}

int find_next_station(int s, int t, vi c) {
    int tip = 0;
    for(auto it : c) {
        if(it < s) tip = 1;
    }
    sort(c.begin(), c.end());
    if(!tip) { /// toti din jur sunt mai mari
        if(t < s || t >= c.back()) return c.back();
        for(auto it : c) {
            if(t <= it) return it;
        }
    } else { // toti din jur sunt mai mici
        if(t > s || t <= c[0]) return c[0];
        reverse(c.begin(), c.end());
        for(auto it : c)
            if(t >= it) return it;
    }
}

Compilation message (stderr)

stations.cpp: In function 'int find_next_station(int, int, vi)':
stations.cpp:88:1: warning: control reaches end of non-void function [-Wreturn-type]
   88 | }
      | ^

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 16 / 16
• Subtask 4: 10 / 10
• Subtask 5: 61 / 61