Submission #706808

#	Time	Username	Problem	Language	Result	Execution time	Memory
706808		rafatoa	Stations (IOI20_stations)	C++17	100 / 100	935 ms	848 KiB

stations

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

vector<int> label(int n, int k, vector<int> u, vector<int> v){
    vector<int> l(n);
    vector<vector<int>> adj(n);
    for(int i=0; i<n-1; i++){
        adj[u[i]].push_back(v[i]);
        adj[v[i]].push_back(u[i]);
    }

    int aux = 0;
    function<void(int, int, int)> dfs = [&](int s, int e, int d){
        if(d%2 == 0) l[s] = aux++;
        for(auto u:adj[s])
            if(u != e) dfs(u, s, d+1);
        if(d%2 == 1) l[s] = aux++;
    };
    dfs(0, -1, 0);
    return l;
}

int find_next_station(int s, int t, vector<int> c){
    sort(c.begin(), c.end());
    int n = c.size();

    if(n == 1) return c[0]; //Out of bounds

    if(s < c[0]){
        if(t < s || t > c[n-2]) return c[n-1];
        for(int i=0; i<n; i++)
            if(c[i] >= t) return c[i];
    } else {
        if(t > s || t < c[1]) return c[0];
        for(int i=2; i<n; i++)
            if(c[i] > t) return c[i-1];
        return c[n-1];
    }
}

Compilation message (stderr)

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

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