Submission #1230516

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230516		Hamed_Ghaffari	Stations (IOI20_stations)	C++20	100 / 100	309 ms	584 KiB

stations

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

const int MXN = 1001;

int timer, stt[MXN], fnt[MXN], h[MXN];
vector<int> g[MXN];

void dfs(int v, int p=-1) {
    stt[v] = timer++;
    for(int u : g[v])
        if(u!=p) {
            h[u] = h[v]^1;
            dfs(u, v);
        }
    fnt[v] = timer++;
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
    for(int i=0; i<n; i++) g[i].clear();
    timer = 0;
    for(int i=0; i<n-1; i++) {
        g[u[i]].push_back(v[i]);
        g[v[i]].push_back(u[i]);
    }
    dfs(0);
    vector<int> ans(n);
    vector<int> cmp;
    for(int i=0; i<n; i++)
        cmp.push_back((h[i]&1) ? fnt[i] : stt[i]);
    sort(cmp.begin(), cmp.end());
    auto GI = [&](int x) {
        return lower_bound(cmp.begin(), cmp.end(), x)-cmp.begin();
    };
    for(int i=0; i<n; i++)
        ans[i] = GI((h[i]&1) ? fnt[i] : stt[i]);
    return ans;
}

int find_next_station(int s, int t, vector<int> c) {
    if(c.size()==1) return c[0];
    if(s<c[0]) { // stt s
        int fn = c[c.size()-2];
        if(s <= t && t <= fn) {
            for(int i : c)
                if(i>=t)
                    return i;
        }
        return c.back();
    }
    else { // fnt s
        int st = c[1]-1;
        if(st <= t && t <= s) {
            for(int i=c.size()-1; i>=0; i--)
                if(c[i]<=t)
                    return c[i];
        }
        return c[0];
    }
}

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