| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 816913 | vjudge1 | Split the Attractions (IOI19_split) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <vector>
#include <algorithm>
#include "attractions.h"
using namespace std;
int sbt = 5;
vector<vector<int> > v;
vector<int> pa, st;
vector<bool> va;
int dfs(int i)
{
va[i] = true;
int s = 1;
for (auto j : v[i])
{
if (j != pa[i] && !va[j])
{
pa[j] = i;
s += dfs(j);
}
}
return s;
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q)
{
vector<int> o = {a, b, c}, r(n, 0);
sort(o.begin(), o.end());
v.resize(n);
pa.resize(n);
st.resize(n);
va.resize(n);
int i, m = p.size();
for (i = 0; i < m; i++)
{
v[p[i]].push_back(q[i]);
v[q[i]].push_back(p[i]);
}
for (i = 0; i < n; i++)
{
pa[i] = -1;
va[i] = false;
}
for (i = 0; i < n; i++)
{
if (v[i].size() > 2)
break;
}
if (n <= 2500 && m <= 5000)
sbt = 4;
if (m == n - 1)
sbt = 3;
if (a == 1)
sbt = 2;
if (i == n)
sbt = 1;
if (sbt == 1)
{
int tf = -1, ts = -1, co = 0;
for (i = 0; i < n; i++)
{
if (v[i].size() == 1)
{
if (tf == -1)
tf = i;
else
{
ts = i;
break;
}
}
}
if (i != n)
dfs(tf);
else
{
dfs(0);
if (pa[v[0][0]] == 0)
ts = v[0][1];
else
ts = v[0][0];
}
for (i = ts; i != -1; i = pa[i])
{
if (co < o[0])
r[i] = 1;
else if (co < o[0] + o[1])
r[i] = 2;
else
r[i] = 3;
co++;
}
}
return r;
}
int main()
{
vector<int> rr = find_split(6, 2, 2, 2, {0, 4, 5, 3, 2, 5}, {1, 2, 3, 4, 1, 0});
for (auto qq : rr)
cout << qq << " ";
return 0;
}