Submission #531304

#	Time	Username	Problem	Language	Result	Execution time	Memory
531304		antonioqbab	Stations (IOI20_stations)	C++14	0 / 100	947 ms	672 KiB

stations

#include <bits/stdc++.h>
#include <stations.h>

using namespace std;

vector<int> label(int n, int k, vector<int> u, vector<int> v){
    int t = 0;
    vector<vector<int>> G(n);
    vector<int> sol(n);
    for(int i=0;i<n-1;++i){
        G[u[i]].emplace_back(v[i]);
        G[v[i]].emplace_back(u[i]);
    }
    function<void(int,int,int)> dfs=[&](int node, int last, int lvl){
    if(!lvl)
        sol[node]=++t;
    for(auto x:G[node])
        if(x!=last)
            dfs(x,node,lvl^1);
    if(lvl)
        sol[node]=++t;
    };
    dfs(0,-1,0);
    return sol;
}

int find_next_station(int s, int f, vector<int> adj){
    int tins, touts, ft;
    int isin=1;
    for(auto x:adj)
        if(x>=s)
            isin=0;
    if(isin)
        tins=s, ft=*max(adj.begin(), adj.end()), touts=ft-1;
    else
        touts=s, ft=*min(adj.begin(),adj.end()), tins=ft+1;
    if(tins<=f&&f<=touts){
        int last = s;
        if(isin)
            sort(adj.begin(),adj.end());
        else
            sort(adj.begin(),adj.end(),greater<int>());
        for(auto x:adj)
        if(x!=ft) {
            int curtin, curtout;
            if(isin)
                curtout=x, curtin=last+1, last=x;
            else
                curtin=x, curtout=last-1, last=x;
            if(curtin<=f&&f<=curtout)
                return x;
        }
    }
    return ft;
}

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