| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 253701 | Erkhemkhuu | Split the Attractions (IOI19_split) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define F first
#define S second
const ll N = 100005;
vector <ll> path, path1;
bool vis[N];
vector <vector <ll> > adj(N);
ll need1, need2;
void dfs(ll v, ll cur) {
path.pb(v);
if(cur == need1 + 1) return;
vis[v] = true;
for(auto &u: adj[v]) {
if(vis[u]) continue;
dfs(u, cur + 1);
}
return;
}
void dfs1(ll v, ll cur) {
path1.pb(v);
if(cur == need2 + 1) return;
vis[v] = true;
for(auto &u: adj[v]) {
if(vis[u]) continue;
dfs1(u, cur + 1);
}
return;
}
void find_split(int n, int a, int b, int c, vector <ll> p, vector <ll> q) {
ll m = p.size();
for(i = 0; i < m; i++) {
adj[p[i]].pb(q[i]);
adj[q[i]].pb(p[i]);
}
vector <ll> vc;
vc = {a, b, c};
sort(vc.begin(), vc.end());
need1 = vc[0];
need2 = vc[1];
dfs(0, 1);
for(i = n - 1; i >= 1; i--) {
if(!vis[i]) {
dfs1(i, 1);
break;
}
}
vector <ll> ans(n, 0);
for(auto &x: path)
ans[x] = 1;
for(auto &x: path1)
ans[x] = 2;
for(i = 0; i < n; i++)
if(!vis[i]) ans[i] = 3;
return ans;
}