Submission #321449

#	Time	Username	Problem	Language	Result	Execution time	Memory
321449		grt	Stations (IOI20_stations)	C++17	100 / 100	936 ms	1284 KiB

stations

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;
using ll = long long;
using pi = pair<int,int>;

#define ST first
#define ND second
#define PB push_back

const int nax = 1000 + 10;
vi V[nax];
bool visited[nax];
int cur;
int num[nax], dep[nax];

void dfs(int x) {
    visited[x] = 1;
    if(dep[x]%2==0) {
        num[x] = cur;
        cur++;
    }
    for(int nbh : V[x]) if(!visited[nbh]) {
        dep[nbh] = dep[x] + 1;
        dfs(nbh);
    }
    if(dep[x]%2==1) {
        num[x] = cur;
        cur++;
    }
}


vi label(int n, int k, vi u, vi v) {
    for(int i = 0; i < n; ++i) {
        visited[i] = 0;
        V[i].clear();
    }
    for(int i = 0; i < n - 1; ++i) {
        V[v[i]].PB(u[i]);
        V[u[i]].PB(v[i]);
    }
    cur = 0;
    dfs(0);
    vi ans(n);
    for(int i = 0; i < n; ++i) ans[i] = num[i];
    return ans;
}

int find_next_station(int s, int y, vi c) {
    if((int)c.size() == 1) return c.back();
    if(s < c[0]) {
        if(y < s || y > c[(int)c.size() - 2]) {
            return c.back();
        }
        int x = 0;
        while(c[x] < y) x++;
        return c[x];
    } else {
        if(y > s || y < c[1]) {
            return c[0];
        }
        int x = (int)c.size() - 1;
        while(y < c[x]) x--;
        return c[x];
    }
}
/*
int main() {
    vi res = label(5, 10, {0, 1, 1, 2}, {1, 2, 3, 4});
    for(int i = 0; i < 5; ++i) cout << res[i] << " ";
    cout << "\n";
    cout << find_next_station(1, 3, {2, 4}) << "\n";
}
*/

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