Submission #305648

#	Time	Username	Problem	Language	Result	Execution time	Memory
305648		jovan_b	Stations (IOI20_stations)	C++17	100 / 100	1161 ms	6008 KiB

stations

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

using namespace std;

vector <int> graf[100005];
vector <int> labels;
int in[100005];
int out[100005];

int tajm;

void dfs(int v, int depth, int par){
    in[v] = ++tajm;
    for(auto c : graf[v]){
        if(c != par){
            dfs(c, depth+1, v);
        }
    }
    out[v] = ++tajm;
    if(depth%2){
        labels[v] = out[v];
    }
    else labels[v] = in[v];
}

map <int, int> koji;

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	labels.clear();
	labels.resize(n);
	for(int i=0; i<n; i++){
        graf[i].clear();
        in[i] = 0;
        out[i] = 0;
	}
	for(int i=0; i<n-1; i++){
        graf[u[i]].push_back(v[i]);
        graf[v[i]].push_back(u[i]);
	}
	dfs(0, 0, -1);
    int tr = -1;
    vector <int> vec;
    for(auto c : labels) vec.push_back(c);
    sort(vec.begin(), vec.end());
    koji.clear();
    for(auto c : vec){
        koji[c] = ++tr;
    }
    for(int i=0; i<n; i++) labels[i] = koji[labels[i]];
	return labels;
}

int find_next_station(int s, int t, std::vector<int> c) {
    if(s < c[0]){
        ///in
        if(s == 0){
            for(auto g : c) if(g >= t) return g;
        }
        int aut = c[c.size()-2];
        if(s <= t && t <= aut){
            for(auto g : c) if(g >= t) return g;
        }
        return c.back();
    }
    /// out
    int iin = c[1];
    if(iin <= t && t <= s){
        for(int j=c.size()-1; j>=1; j--){
            if(c[j] <= t) return c[j];
        }
    }
    return c[0];
}

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