Submission #1230065

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230065		dssfsuper2	Stations (IOI20_stations)	C++20	0 / 100	308 ms	612 KiB

stations

#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
using pii = pair<int, int>;
int timer;
vector<int> tin, tout;
vector<pii> rv2;
vector<vector<int>> adj;
void dfs(int node, int p, int md2){
	timer++;
    tin[node]=timer;
    for(auto thing:adj[node]){
        if(thing!=p)dfs(thing, node, md2^1);
    }
	timer++;
    tout[node]=timer;
    rv2[node].first=(md2==0? tin[node]: tout[node]);
}
vector<int> label(int n, int k, vector<int> u, vector<int> v){
    tin.assign(n, 0);tout.assign(n,0);rv2.assign(n, {0, 0});adj.assign(n, {});
    timer=0;
    for(int i = 0;i<n-1;i++){
        rv2[i].second=i;
        adj[u[i]].push_back(v[i]);
        adj[v[i]].push_back(u[i]);
    }
    dfs(0, -1, 0);
    sort(all(rv2));
    vector<int> reala(n);
    for(int i = 0;i<n;i++){
        reala[rv2[i].second]=i;
    }
    return reala;
}
int find_next_station(int s, int t, vector<int> c){
    if(c.size()==1)return c[0];
    int n = c.size();
    for(auto thing:c)if(thing==t)return t;
    if (s<c[0]){
        //s entry c exits
        int mye = c[n-2];
        if (t<s || t>mye)return c[n-1];
        for(auto thing:c)if(thing>=t)return thing;
    }
    else{
        int mye = c[1];
        if (t<mye || t>s)return c[0];
        for(int i = c.size()-1;i>=0;i--)if(c[i]<=t)return c[i];
    }
    assert(false);
}

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