# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1224886 | nickolasarapidis | Split the Attractions (IOI19_split) | C++17 | 0 ms | 0 KiB |
#include "split.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
vector<int> adj[MAXN];
vector<int> id(MAXN, 0);
vector<bool> visited(MAXN, false);
int cnt = 0, As, Bs, Cs;
void dfs(int s){
if(visited[s]) return;
visited[s];
id[s] = 2;
cnt++;
for(auto u : adj[s]){
if(cnt < Bs) dfs(u);
}
}
vector<int> find_split(int N, int A, int B, int C, vector<int> p, vector<int> q){
As = A; Bs = B; Cs = C;
for(int i = 0; i < p.size(); i++){
adj[p[i]].push_back(q[i]);
adj[q[i]].push_back(p[i]);
}
if(p.size() == N - 1){
for(int i = 0; i < A; i++){
id[i] = 1;
}
for(int i = A; i < A + B; i++){
id[i] = 2;
}
for(int i = B; i < N; i++){
id[i] = 3;
}
}
else{
bool a = false;
dfs(0);
for(int i = 0; i < N; i++){
if(id[i] != 2){
id[i] = 3;
if(a != true){
id[i] = 1;
a = true;
}
}
}
}
vector<int> s(N);
for(int i = 0; i < N; i++){
ans[i] = id[i];
}
return ans;
}