제출 #1046201

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1046201		VMaksimoski008	Stations (IOI20_stations)	C++17	100 / 100	546 ms	1064 KiB

stations

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

const int maxn = 1005;
vector<int> graph[maxn], L;
int timer = 0;

void dfs(int u, int p, int d) {
    if(!d) L[u] = timer++;
    for(int &v : graph[u]) if(v != p) dfs(v, u, d ^ 1);
    if(d) L[u] = timer++;
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
    for(int i=0; i<n; i++) graph[i].clear(), timer = 0;
    for(int i=0; i<n-1; i++) {
        graph[u[i]].push_back(v[i]);
        graph[v[i]].push_back(u[i]);
    }
    L.clear();
	L.resize(n);
    dfs(0, 0, 0);
    return L;
}

int find_next_station(int s, int t, vector<int> c) {
    if(c[0] < s) {
        if(s < t || t < c[0]) return c[0];
        return c[upper_bound(c.begin(), c.end(), t)-c.begin()-1];
    }
    
    if(c.back() < t || t < s) return c.back();
    return c[lower_bound(c.begin(), c.end(), t)-c.begin()];
}   

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