| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1310934 | altayeb_132 | 기지국 (IOI20_stations) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
using namespace std;
int indg[1001], ans[1001];
vector<int> adj[1001];
int t1 = 0;
void dfs(int n, int pr)
{
ans[n] = t1++;
for(auto i : adj[n])
if(i != pr)
dfs(i, n);
}
vector<int> label(int n, int k, vector<int> u, vector<int> v)
{
for(int i = 0; i < n; i++)
{
adj[i].clear();
indg[i] = 0;
}
t1 = 0;
vector<int> labels(n);
for(int i = 0; i < n - 1; i++)
{
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
indg[v[i]]++;
indg[u[i]]++;
}
for(int i = 0; i < n; i++)
{
if(indg[i] == 1)
{
dfs(i, -1);
break;
}
}
for (int i = 0; i < n; i++)
{
labels[i] = ans[i];
}
return labels;
}
int find_next_station(int s, int t, std::vector<int> c)
{
if(c.size() == 1)
return c[0];
if(s < t)
return max(c[0], c[1]);
else
return min(c[0], c[1]);
}
int main()
{
int n, k;
cin >> n >> k;
vector<int> u1(n - 1), v1(n - 1);
for(int i = 0; i < n - 1; i++)
{
int u, v;
cin >> u >> v;
u1[i] = u; v1[i] = v;
}
label(n, k, u1, v1);
// cout << 1;
// for(int i = 0; i < n; i++)
// cout << ans[i] << ' ';
cout << find_next_station(3, 1, {0, 2});
}
