# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
290569 | jairRS | Split the Attractions (IOI19_split) | C++17 | 87 ms | 9464 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "split.h"
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
vvi adj;
vi degree;
int ga, gb, gc;
vector<bool> visited(200000);
void dfs(int src, int prev = -1)
{
if (visited[src])
return;
visited[src] = true;
if (gc > 0)
{
degree[src] = 3;
gc--;
}
else if (gb > 0)
{
degree[src] = 2;
gb--;
}
else if (ga > 0)
{
degree[src] = 1;
ga--;
}
for (int a : adj[src])
{
if (a != prev)
{
dfs(a, src);
break;
}
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q)
{
ga = a;
gb = b;
gc = c;
degree = vi(n, 0);
adj = vvi(n);
for (int i = 0; i < p.size(); i++)
{
adj[p[i]].push_back(q[i]);
adj[q[i]].push_back(p[i]);
degree[p[i]]++;
degree[q[i]]++;
}
bool loop = true;
for (int i = 0; i < n; i++)
{
if (degree[i] == 1)
{
dfs(i);
loop = false;
break;
}
}
if (loop)
dfs(0);
return degree;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |