| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 880874 | Lib | Split the Attractions (IOI19_split) | C++14 | 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 <bits/stdc++.h>
#include "split.h"
using namespace std;
vector <vector <int> > adj;
vector <vector <int> > cadj;
vector <vector <int> > tadj;
vector <int> TVector;
int cpos[200003];
int check[200003];
int SubtreeSize[200003];
int Parent[200003];
int n;
//Parent on each iteration of DFS
deque <int> clist;
vector <int> ans;
int csize;
int cback;
vector <int> Group1,Group2;
int GroupAID,GroupBID,GroupASize,GroupBSize;
int cur;
int Subtree1,Subtree2;
void ShittyDFS(int i){
cadj.clear();
tadj=adj;
for(int k=0;k<=n+1;k++){
cpos[k]=0;
SubtreeSize[k]=0;
Parent[k]=0;
cadj.push_back(TVector);
}
cadj.push_back(TVector);
Parent[i]=-1;
//wacky dfs (and calculate size of subtrees as well
//have to opt into a less retarded DFS to see whether things will work out or not.
cur=1;
clist.push_back(i);
check[i]=1;
while(!clist.empty()){
if(!SubtreeSize[clist.back()]){
SubtreeSize[clist.back()]=cur;
}
while(!adj[clist.back()].empty&&check[adj[clist.back()].back()]){
adj[clist.back()].pop_back();
}
if(!adj[clist.back()].empty()&&!check[adj[clist.back()].back()]){
check[adj[clist.back()].back()]=1;
Parent[adj[clist.back()].back()]=clist.back();
cback=clist.back();
cadj[clist.back()].push_back(adj[clist.back()].back());
cadj[adj[clist.back()].back()].push_back(clist.back());
clist.push_back(adj[cback][cpos[cback]]);
cur++;
}else{
SubtreeSize[clist.back()]=cur-SubtreeSize[clist.back()];
clist.pop_back();
}
}
}
vector <int> find_split(int n, int a, int b, int c, vector <int> p, vector <int> q){
//Only cares about the 2 smaller group: Assuming that we DID find a solution where the largest group is connected, just swap some of those points for the unused group.
//As this is the largest group, swapping some minor connected parts for the unused group is still valid, and always doable => only care about 2 smallest group only
//very intuitive tbh
vector <pair <int,int> > order;
order.push_back({a,1});
order.push_back({b,2});
order.push_back({c,3});
sort(order.begin(),order.end());
GroupAID=order[0].second;
GroupASize=order[0].first;
GroupBID=order[1].second;
GroupBSize=order[1].first;
for(int i=0;i<=n+1;i++){
adj.push_back(TVector);
}
//Build the graph. Who can't understand this?
for(int i=0;i<p.size();i++){
adj[p[i]].push_back(q[i]);
adj[q[i]].push_back(p[i]);
}
/*
Let's just call the smallest group gropu A, and second smallest group group B.
Let's kinda start working with the tree subtask first. When we split the tree into 2 part, we are essentially dedicating an entire subtree for group A and the rest of the
tree for group B, or vice versa. We will now do the following:\
- Try all vertices on the tree. For each verticies, check through all of its subtreees.
- If we can dedicate an entire subtree to group A and the rest to group B (or vice versa), this split will work instantly. We are basically cutting our original tree into 2 parts.
- If after checking all subtrees of all vertices and we still haven't found a solution, there is no solution.
(Why this kind of check works: We are trying everything, so no method of "splitting OG tree into 2 parts" is ignored...Let's be honest, I think that 64pts for this is trivial and
doesn't require much thought at all. The wacky funny parts comes from the final subtask, which I haven't solved yet.
Complexity: We take O(N) to DFS and calculate size of subtrees of all nodes. For each of the N vertex, we check through all of their adjacient vertices. Basically, we are checking
3N times (like, come on, in a tree of N nodes, there are 2N-2 pairs of adjacient points. There is literally nothing to explain here). Basically, for each DFS tree, we take roughly
O(N) to check whether there exists a valid split or not.
For the general graph (but small) case: Just create N DFS trees and bruteforce them, lol. Nothing to talk about just yet
*/
for(int i=0;i<n;i++){
//Tested locally, seems correct enough. First time implementing DFS. Moving on.
//On another hand, you know what? Chugging DFS into a function now. brb
//Done
cadj.clear();
ShittyDFS(i);
//Try the split with every single vertex on the tree.
for(int k=0;k<n;k++){
check[k]=0;
}
//Oh, one major note: The things below will have to be done on the DFS tree created on the previous step. Instead of BFS-ing on the original graph
//(which is the adj vector of edges), I will BFS on cadj (the graph that is the DFS tree created in this iteration)
for(int k=0;k<n;k++){
for(int l=0;l<cadj[k].size();l++){
Subtree1=SubtreeSize[cadj[k][l]];
if(cadj[k][l]==Parent[k]){
Subtree1=n-SubtreeSize[k];
}
Subtree2=n-Subtree1;
if(Subtree1>=GroupASize&&Subtree2>=GroupBSize){
//Found the answer so just BFS to mark the points
check[cadj[k][l]]=GroupAID;
check[k]=GroupBID;
clist.clear();
clist.push_back(cadj[k][l]);
csize=1;
while(csize<GroupASize){
for(int d=0;d<cadj[clist.front()].size();d++){
if(!check[cadj[clist.front()][d]]){
check[cadj[clist.front()][d]]=GroupAID;
clist.push_back(cadj[clist.front()][d]);
csize++;
if(csize==GroupASize){
break;
}
}
if(csize==GroupASize){
break;
}
}
clist.pop_front();
}
clist.clear();
clist.push_back(k);
csize=1;
while(csize<GroupBSize){
for(int d=0;d<cadj[clist.front()].size();d++){
if(!check[cadj[clist.front()][d]]){
check[cadj[clist.front()][d]]=GroupBID;
clist.push_back(cadj[clist.front()][d]);
csize++;
if(csize==GroupBSize){
break;
}
}
if(csize==GroupBSize){
break;
}
}
clist.pop_front();
}
for(int d=0;d<n;d++){
if(check[d]==0){
check[d]=6-GroupAID-GroupBID;
}
ans.push_back(check[d]);
}
return ans;
}
swap(GroupASize,GroupBSize);
swap(GroupAID,GroupBID);
//Assign the other way around: (subtree of k) to part B, the rest to A.
if(Subtree1>=GroupASize&&Subtree2>=GroupBSize){
//Found the answer so just BFS to mark the points
check[cadj[k][l]]=GroupAID;
check[k]=GroupBID;
clist.clear();
clist.push_back(cadj[k][l]);
csize=1;
while(csize<GroupASize){
for(int d=0;d<cadj[clist.front()].size();d++){
if(!check[cadj[clist.front()][d]]){
check[cadj[clist.front()][d]]=GroupAID;
clist.push_back(cadj[clist.front()][d]);
csize++;
if(csize==GroupASize){
break;
}
}
if(csize==GroupASize){
break;
}
}
clist.pop_front();
}
clist.clear();
clist.push_back(k);
csize=1;
while(csize<GroupBSize){
for(int d=0;d<cadj[clist.front()].size();d++){
if(!check[cadj[clist.front()][d]]){
check[cadj[clist.front()][d]]=GroupBID;
clist.push_back(cadj[clist.front()][d]);
csize++;
if(csize==GroupBSize){
break;
}
}
if(csize==GroupBSize){
break;
}
}
clist.pop_front();
}
for(int d=0;d<n;d++){
if(check[d]==0){
check[d]=6-GroupAID-GroupBID;
}
//check[d]=1;
ans.push_back(check[d]);
//cout<<check[d]<<" ";
}
return ans;
}
}
}
}
for(int i=0;i<n;i++){
ans.push_back(0);
}
return ans;
}