| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 836183 | penguinman | 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>
#ifndef EVAL
#include "grader.cpp"
#endif
using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::string;
using ll = long long;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;
#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define all(a) a.begin(),a.end()
#define pb emplace_back
#define mp std::make_pair
#define mtp std::make_tuple
constexpr ll inf = (1ll<<60);
vector<int> subtask_4(int n, int a, int b, int c, std::vector<int> p, std::vector<int> q){
ll N = n;
vector<pii> data = {mp(a,1), mp(b,2), mp(c,3)};
sort(all(data));
vii edge(N);
rep(i,0,p.size()){
edge[p[i]].pb(q[i]);
edge[q[i]].pb(p[i]);
}
vector<int> ans(N, data[2].second);
auto modify_all = [&](){
rep(i,0,2){
rep(j,0,N){
if(ans[j] == data[i].second){
vector<bool> visited(N);
ll cnt = 0;
std::function<void(ll)> modify = [&](ll now){
if(cnt < data[i].first){
cnt++;
}
else{
ans[now] = data[2].second;
}
visited[now] = true;
for(auto next: edge[now]){
if(visited[next]) continue;
if(ans[next] != data[i].second) continue;
modify(next);
}
};
modify(j);
break;
}
}
}
return;
};
rep(i,0,N){
vector<bool> used(N);
used[i] = true;
vii v;
for(auto next: edge[i]){
if(used[next]) continue;
vi c;
std::function<void(ll)> dfs = [&](ll now){
c.pb(now);
used[now] = true;
for(auto nex: edge[now]){
if(used[nex]) continue;
dfs(nex);
}
};
dfs(next);
v.pb(c);
}
ll sum = 1;
rep(j,0,v.size()){
sum += v[j].size();
}
rep(j,0,v.size()){
if(v[j].size() < data[0].first) continue;
if(sum-v[j].size() < data[1].first) continue;
rep(k,0,v.size()){
if(j == k) continue;
for(auto el: v[k]) ans[el] = data[1].second;
}
ans[i] = data[1].second;
for(auto el: v[j]) ans[el] = data[0].second;
modify_all();
return ans;
}
rep(j,0,v.size()){
if(v[j].size() < data[1].first) continue;
if(sum-v[j].size() < data[0].first) continue;
rep(k,0,v.size()){
if(j == k) continue;
for(auto el: v[k]) ans[el] = data[0].second;
}
ans[i] = data[0].second;
for(auto el: v[j]) ans[el] = data[1].second;
modify_all();
return ans;
}
}
ans.assign(N,0);
return ans;
}
struct union_find{
ll N;
vi par;
union_find(int n): N(n){
par.resize(N);
rep(i,0,N) par[i] = i;
}
ll root(ll now){
if(par[now] == now) return now;
return par[now] = root(par[now]);
}
bool same(ll l, ll r){
return root(l) == root(r);
}
void merge(ll l, ll r){
l = root(l);
r = root(r);
if(l == r) return;
par[l] = r;
}
};
vector<int> subtask_1_2_3(int n, int a, int b, int c, std::vector<int> p, std::vector<int> q){
ll N = n;
vector<pii> data = {mp(a,1), mp(b,2), mp(c,3)};
sort(all(data));
vii edge(N);
union_find tree(N);
rep(i,0,p.size()){
if(tree.same(p[i], q[i])) continue;
tree.merge(p[i], q[i]);
edge[p[i]].pb(q[i]);
edge[q[i]].pb(p[i]);
}
vector<int> ans(N, data[2].second);
auto modify_all = [&](){
rep(i,0,2){
rep(j,0,N){
if(ans[j] == data[i].second){
vector<bool> visited(N);
ll cnt = 0;
std::function<void(ll)> modify = [&](ll now){
if(cnt < data[i].first){
cnt++;
}
else{
ans[now] = data[2].second;
}
visited[now] = true;
for(auto next: edge[now]){
if(visited[next]) continue;
if(ans[next] != data[i].second) continue;
modify(next);
}
};
modify(j);
break;
}
}
}
return;
};
vi subtree(N);
std::function<void(ll)> dfs_subtree = [&](ll now){
subtree[now] = 1;
for(auto next: edge[now]){
if(subtree[next]) continue;
dfs_subtree(next);
subtree[now] += subtree[next];
}
};
dfs_subtree(0);
std::function<void(ll, ll)> dfs_coloring = [&](ll now, ll color){
ans[now] = color;
for(auto next: edge[now]){
if(subtree[next] > subtree[now]) continue;
dfs_coloring(next, color);
}
};
rep(i,1,N){
if(subtree[i] < data[0].first) continue;
if(N-subtree[i] < data[1].first) continue;
ans.assign(N,data[1].second);
dfs_coloring(i, data[0].second);
modify_all();
return ans;
}
rep(i,1,N){
if(subtree[i] < data[1].first) continue;
if(N-subtree[i] < data[0].first) continue;
ans.assign(N, data[0].second);
dfs_coloring(i, data[1].second);
modify_all();
return ans;
}
ans.assign(N,0);
return ans;
}
std::vector<int> find_split(int n, int a, int b, int c, std::vector<int> p, std::vector<int> q) {
return subtask_1_2_3(n,a,b,c,p,q);
}