| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 832215 | tranxuanbach | Split the Attractions (IOI19_split) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "split.h"
#include <bits/stdc++.h>
using namespace std;
#define isz(a) ((signed)a.size())
const int N = 1e5 + 5, M = 2e5 + 5;
int n, m;
vector <pair <int, int>> vcolor;
vector <int> adj[N];
vector <int> ans;
namespace subtask12{
bool check(){
for (auto &[cnt, col]: vcolor){
if (col == 1 and cnt == 1){
return true;
}
}
for (int u = 0; u < n; u++){
if (isz(adj[u]) > 2){
return false;
}
}
return true;
}
vector <bool> chosen;
void dfs(int u){
chosen[u] = true;
ans[u] = vcolor.back().second;
vcolor.back().first--;
if (vcolor.back().first == 0){
vcolor.pop_back();
}
for (auto v: adj[u]){
if (chosen[v]){
continue;
}
dfs(v);
}
}
vector <int> solve(){
chosen.assign(n, false);
int s = 0;
for (int u = 1; u < n; u++){
if (isz(adj[u]) == 1){
s = u;
break;
}
}
dfs(s);
return ans;
}
}
vector <int> find_split(int _n, int _a, int _b, int _c, vector <int> _u, vector <int> _v){
n = _n; m = isz(_u);
vcolor = {{a, 1}, {b, 2}, {c, 3}};
sort(vcolor.begin(), vcolor.end());
for (int i = 0; i < m; i++){
int u = _u[i], v = _v[i];
adj[u].emplace_back(v);
adj[v].emplace_back(u);
}
ans.assign(n, 0);
if (subtask12::check()){
return subtask12::solve();
}
}