Submission #880376

#	Time	Username	Problem	Language	Result	Execution time	Memory
880376		Lib	Split the Attractions (IOI19_split)	C++14	0 / 100	3 ms	4700 KiB

split

#include <bits/stdc++.h>
#include "split.h"
using namespace std;
vector <vector <int> > adj;
vector <vector <int> > cadj;
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;
	vector <int> Group1,Group2;
	int GroupAID,GroupBID,GroupASize,GroupBSize;
	int cur;
int Subtree1,Subtree2;
void ShittyDFS(int i){
	cadj.clear();
	for(int k=0;k<n;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
		cur=1;
		clist.push_back(i);
		check[i]=1;
		while(!clist.empty()){
			if(!SubtreeSize[clist.back()]){
				SubtreeSize[clist.back()]=cur;
			}
			while(cpos[clist.back()]<adj[clist.back()].size()&&check[adj[clist.back()][cpos[clist.back()]]]){
				cpos[clist.back()]++;
			}
			if(cpos[clist.back()]<adj[clist.back()].size()&&!check[adj[clist.back()][cpos[clist.back()]]]){
				check[adj[clist.back()][cpos[clist.back()]]]=1;
				Parent[adj[clist.back()][cpos[clist.back()]]]=clist.back();
				cadj[clist.back()].push_back(adj[clist.back()][cpos[clist.back()]]);
				cadj[adj[clist.back()][cpos[clist.back()]]].push_back(clist.back());
				clist.push_back(adj[clist.back()][cpos[clist.back()]]);
				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
		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;
}

Compilation message (stderr)

split.cpp: In function 'void ShittyDFS(int)':
split.cpp:38:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |    while(cpos[clist.back()]<adj[clist.back()].size()&&check[adj[clist.back()][cpos[clist.back()]]]){
      |          ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
split.cpp:41:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |    if(cpos[clist.back()]<adj[clist.back()].size()&&!check[adj[clist.back()][cpos[clist.back()]]]){
      |       ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:71:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |  for(int i=0;i<p.size();i++){
      |              ~^~~~~~~~~
split.cpp:102:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |    for(int l=0;l<cadj[k].size();l++){
      |                ~^~~~~~~~~~~~~~~
split.cpp:116:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |       for(int d=0;d<cadj[clist.front()].size();d++){
      |                   ~^~~~~~~~~~~~~~~~~~~~~~~~~~~
split.cpp:135:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |       for(int d=0;d<cadj[clist.front()].size();d++){
      |                   ~^~~~~~~~~~~~~~~~~~~~~~~~~~~
split.cpp:169:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  169 |       for(int d=0;d<cadj[clist.front()].size();d++){
      |                   ~^~~~~~~~~~~~~~~~~~~~~~~~~~~
split.cpp:188:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  188 |       for(int d=0;d<cadj[clist.front()].size();d++){
      |                   ~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 11
• Subtask 3: 0 / 22
• Subtask 4: 0 / 24
• Subtask 5: 0 / 36