Submission #1244480

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244480		guagua0407	Stations (IOI20_stations)	C++20	100 / 100	306 ms	620 KiB

stations

#include "stations.h"
//#include "stub.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define all(x) x.begin(),x.end()

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	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]);
    }
    vector<int> st(n),en(n);
    vector<int> d(n);
    int timer=-1;
    function<void(int,int)> dfs=[&](int v,int p){
        st[v]=++timer;
        for(auto u:adj[v]){
            if(u==p) continue;
            d[u]=d[v]+1;
            dfs(u,v);
        }
        en[v]=timer;
    };
    dfs(0,-1);
    vector<pair<pair<int,int>,pair<int,int>>> ord;
    for(int i=0;i<n;i++){
        if(d[i]%2==0) ord.push_back({{st[i],0},{-d[i],i}});
        else ord.push_back({{en[i],0},{-d[i],i}});
    }
    sort(all(ord));
    vector<int> label(n);
    for(int i=0;i<n;i++){
        label[ord[i].s.s]=i;
    }
	return label;
}

int find_next_station(int S, int T, std::vector<int> C) {
    vector<int> c=C;
    bool even=true;
	for(auto v:c){
        if(v<S) even=false;
    }
    int l,r;
    if(even){
        l=S;
        sort(all(c));
        if((int)c.size()==1) r=l;
        else r=c[(int)c.size()-2];
    }
    else{
        r=S;
        sort(all(c));
        if((int)c.size()==1) l=r;
        else l=c[1];
    }
    if(l<=T and T<=r){
        if(even){
            for(auto v:c){
                if(T<=v) return v;
            }
        }
        else{
            reverse(all(c));
            for(auto v:c){
                if(v<=T) return v;
            }
        }
    }
    else{
        for(auto v:c){
            if(v<l or r<v) return v;
        }
    }
    assert(false);
}

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