| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 589455 | Soumya1 | Rectangles (IOI19_rect) | C++17 | 0 ms | 0 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"
#include <bits/stdc++.h>
#ifdef __LOCAL__
#include <debug_local.h>
#endif
using namespace std;
const int mxN = 1e5 + 5;
vector<int> ad[mxN];
bool vis[mxN];
int need;
vector<int> s1;
void dfs(int u) {
vis[u] = true;
if (s1.size() == need) return;
s1.push_back(u);
for (int v : ad[u]) {
if (vis[v]) continue;
dfs(v);
}
}
int sz[mxN], in[mxN], out[mxN], timer;
void dfs1(int u, int p) {
in[u] = ++timer;
sz[u] = 1;
for (int v : ad[u]) {
if (v == p) continue;
dfs1(v, u);
sz[u] += sz[v];
}
out[u] = timer;
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
for (int i = 0; i < p.size(); i++) {
ad[p[i]].push_back(q[i]);
ad[q[i]].push_back(p[i]);
}
if (p.size() == n - 1) {
vector<pair<int, int>> choice = {{a, 1}, {b, 2}, {c, 3}};
sort(choice.begin(), choice.end());
int A = choice[0].first;
int B = choice[1].first;
vector<int> ans(n, choice[2].second);
dfs1(0, -1);
for (int i = 0; i < n - 1; i++) {
if (in[p[i]] <= in[q[i]] && out[q[i]] <= out[p[i]]) swap(p[i], q[i]);
if (sz[p[i]] >= A && n - sz[p[i]] >= B) {
need = A;
for (int j = 0; j < n; j++) vis[j] = !(in[j] >= in[p[i]] && out[j] <= out[p[i]]);
dfs(p[i]);
for (int j : s1) ans[j] = choice[0].second;
memset(vis, 0, sizeof vis);
s1.clear();
need = B;
for (int j = 0; j < n; j++) vis[j] = (in[j] >= in[p[i]] && out[j] <= out[p[i]]);
dfs(q[i]);
for (int j : s1) ans[j] = choice[1].second;
return ans;
}
if (sz[p[i]] >= B && n - sz[p[i]] >= A) {
need = B;
for (int j = 0; j < n; j++) vis[j] = !(in[j] >= in[p[i]] && out[j] <= out[p[i]]);
dfs(p[i]);
for (int j : s1) ans[j] = choice[1].second;
memset(vis, 0, sizeof vis);
s1.clear();
need = A;
for (int j = 0; j < n; j++) vis[j] = (in[j] >= in[p[i]] && out[j] <= out[p[i]]);
dfs(q[i]);
for (int j : s1) ans[j] = choice[0].second;
return ans;
}
}
ans.assign(n, 0);
return ans;
}
if (a == 1) {
vector<int> ans(n, 3);
need = b;
dfs(1);
for (int i : s1) ans[i] = 2;
for (int i = 0; i < n; i++) {
if (ans[i] == 3) {
ans[i] = 1;
break;
}
}
return ans;
}
int start = 0;
vector<int> deg(n);
for (int i : p) deg[i]++;
for (int i : q) deg[i]++;
for (int i = 0; i < n; i++) {
if (deg[i] == 1) start = i;
}
vector<int> ans(n);
int cur = 0;
while (!ans[start]) {
cur++;
if (cur <= a) ans[start] = 1;
else if (cur <= a + b) ans[start] = 2;
else ans[start] = 3;
for (int to : ad[start]) {
if (!ans[to]) start = to;
}
}
return ans;
}