Submission #881418

#	Time	Username	Problem	Language	Result	Execution time	Memory
881418		Lib	Split the Attractions (IOI19_split)	C++14	40 / 100	538 ms	26996 KiB

split

#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 check[300003];
int SubtreeSize[300003];
int Parent[300003];
int n;
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();
	adj=tadj;
	for(int k=0;k<N;k++){
			SubtreeSize[k]=0;
			Parent[k]=0;
			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.
		//it does. good
		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()]=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].back());
				cur++;
			}else{
				SubtreeSize[clist.back()]=cur-SubtreeSize[clist.back()]+1;
				//while(!clist.empty()&&adj[clist.back()].empty()){
					clist.pop_back();
				//}
			}
		}
		//retarded fucker deleted everything outta the graph after 1st instance of DFS. Has to DFS N times. Doesn't understand why the DFS refuses to work correctly
		//It is, indeed, very highly recommended to NOT use IOI tasks to learn the basics :wheeze: :holyfuck:
}
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
	N=n;
	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;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]);
	}
	//Maybe random shuffle would work????
	for(int i=0;i<n;i++){
	//	random_shuffle(adj[i].begin(),adj[i].end());
	}
	tadj=adj;
	/*
	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();
					}
					ans.clear();
					for(int d=0;d<N;d++){
						if(check[d]==0){
							check[d]=6-GroupAID-GroupBID;
						}
						ans.push_back(check[d]);
					}
					return ans;
				}
				//As it turns out, considering the reverse situation isn't needed. ok.
				//Still can't figure out wtf is stopping this from passing subtask 4 for the life of me
				//Or maybe it is indeed needed??
				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]);
					}
					return ans;
				}
				
			}
		}
		if(p.size()==N-1){
			//If it is a tree, the DFS tree is always the same, so 1 DFS is all it needs.
			break;
		}
	}
	ans.clear();
	for(int i=0;i<N;i++){
		ans.push_back(0);
	}
	return ans;
}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:80:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |  for(int i=0;i<p.size();i++){
      |              ~^~~~~~~~~
split.cpp:116:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |    for(int l=0;l<cadj[k].size();l++){
      |                ~^~~~~~~~~~~~~~~
split.cpp:130:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |       for(int d=0;d<cadj[clist.front()].size();d++){
      |                   ~^~~~~~~~~~~~~~~~~~~~~~~~~~~
split.cpp:149:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |       for(int d=0;d<cadj[clist.front()].size();d++){
      |                   ~^~~~~~~~~~~~~~~~~~~~~~~~~~~
split.cpp:187:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  187 |       for(int d=0;d<cadj[clist.front()].size();d++){
      |                   ~^~~~~~~~~~~~~~~~~~~~~~~~~~~
split.cpp:206:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  206 |       for(int d=0;d<cadj[clist.front()].size();d++){
      |                   ~^~~~~~~~~~~~~~~~~~~~~~~~~~~
split.cpp:233:14: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  233 |   if(p.size()==N-1){
      |      ~~~~~~~~^~~~~

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