제출 #736125

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
736125		onlk97	기지국 (IOI20_stations)	C++14	0 / 100	937 ms	652 KiB

stations

#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
vector <int> g[1010];
int fa[1010],sz[1010],hson[1010];
void dfs1(int cur,int prv){
    fa[cur]=prv;
    sz[cur]=1;
    int mxz=-1;
    for (int i:g[cur]){
        if (i==prv) continue;
        dfs1(i,cur);
        if (sz[i]>mxz){
            mxz=sz[i];
            hson[cur]=i;
        }
    }
}
int id[1010];
int curidx;
void dfs2(int cur){
    curidx++;
    id[cur]=curidx;
    if (!hson[cur]) return;
    dfs2(hson[cur]);
    for (int i:g[cur]){
        if (i!=fa[cur]&&i!=hson[cur]) dfs2(i);
    }
}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
    for (int i=0; i<=n; i++){
        fa[i]=0; sz[i]=0; hson[i]=0;
        g[i].clear(); id[i]=0;
    }
    curidx=0;
	for (int i=0; i<n-1; i++){
        g[u[i]+1].push_back(v[i]+1);
        g[v[i]+1].push_back(u[i]+1);
    }
    dfs1(1,0);
    dfs2(1);
    vector <int> ans(n);
    for (int i=0; i<n; i++) ans[i]=id[i+1];
    return ans;
}

int find_next_station(int s, int t, std::vector<int> c) {
	for (int i:c){
        if (i==t) return t;
    }
    if (t<s){
        for (int i:c){
            if (i<s) return i;
        }
    }
    int mx=-1;
    for (int i:c){
        if (i<t) mx=max(mx,i);
    }
    return mx;
}

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