Submission #366146

#	Time	Username	Problem	Language	Result	Execution time	Memory
366146		79brue	Stations (IOI20_stations)	C++14	100 / 100	1067 ms	1244 KiB

stations

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

using namespace std;

typedef long long ll;

vector<int> link[1002];
bool visited[1002];
int arr[1002];
int sz[1002];

void szd(int x, int par=-1){
    sz[x] = 1;
    for(auto y: link[x]){
        if(y == par) continue;
        szd(y, x);
        sz[x] += sz[y];
    }
}

void dfs(int x, int l, int r, bool chk){
    visited[x] = 1;
    if(chk) arr[x] = l++;
    else arr[x] = r--;
    for(auto y: link[x]){
        if(visited[y]) continue;
        if(chk){
            dfs(y, r-sz[y]+1, r, !chk);
            r -= sz[y];
        }
        else{
            dfs(y, l, l+sz[y]-1, !chk);
            l += sz[y];
        }
    }
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
    fill(visited, visited+n, 0);
    fill(arr, arr+n, 0);
    fill(sz, sz+n, 0);
    for(int i=0; i<n; i++) link[i].clear();
    for(int i=0; i<n-1; i++) link[u[i]].push_back(v[i]), link[v[i]].push_back(u[i]);

    szd(0);
    dfs(0, 0, n-1, 1);

    return vector<int> (arr, arr+n);
}

int find_next_station(int s, int t, vector<int> c) {
    if(s == 0){ /// 루트
        sort(c.begin(), c.end());
        for(auto x: c){
            if(t <= x) return x;
        }
        exit(1);
    }
	else if(c[0] > s){ /// 작은 정점
        sort(c.begin(), c.end());
        if(t < s) return c.back();
        for(auto x: c){
            if(t <= x) return x;
        }
        return c.back();
	}
	else{ /// 큰 정점
        sort(c.rbegin(), c.rend());
        if(t > s) return c.back();
        for(auto x: c){
            if(t >= x) return x;
        }
        return c.back();
	}
}

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