제출 #883376

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
883376		Lib	Split the Attractions (IOI19_split)	C++14	40 / 100	92 ms	26176 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;
int GetSubtreeSize(int i, int k){
	//New function to make considering cases easier
	if(cadj[i][k]!=Parent[i]){
		return SubtreeSize[cadj[i][k]];
	}else{
		return N-SubtreeSize[i];
	}
}
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
	*/
	
	/*
	Don't actually have to DFS N times - once is enough. After figuring out the full solution I could finally understand why noone goes for a 64 in this. I actually can't even
	understand how to get 64 in this. 
	*/
	int IsCentroid;
	for(int i=0;i<1;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.
		/*
		Actually, no. Just trying the split in the centroid is enough. Come on, this task is asking about the amount of vertices on some subtree. That kind of shit is bound to
		be related to centroid somehow. If what we're considering is a tree (which is the case for subtask 3), it is easy to proof that: If no split exists at the centroid of the
		tree, then no valid split would exist.
		Proof: Again, we assume a<=b<=c. What we've been doing for subtask 3 is essentially dedicate an entire subtree to group A. If there exists one subtree (when our tree
		is rooted at the centroid of the DFS tree) with size at least a, good, dedicate this entire subtree to group A. As the other subtrees are still connected to eachother
		through the centroid, we can easily assign the rest of these subtrees to group B. As the upper limit of a is [N/3] and the size of each subtree when we root the tree at the
		centroid is at most [N/2], it is trivial to show that we still have enough vertices left after assigning an entire subtree to group A to assign to group B.
		
		It is also trivial to proof that: When we root the DFS tree (which is just.....our original tree) at its centroid, if we can't find a valid split there, no valid split exists.
		Proof: Again, note that if the split at the centroid fail, it means that there doesn't exist a subtree with size > a. In order for a valid group A to exist, we'll have to
		"merge" at least 2 subtrees with eachother, connecting them through the centroid. After merging some subtrees to assign them to group A, we are left with a bunch of disconnected
		subtrees (as the centroid is already used to link the group of previously selected subtrees together) and a completed group A.
		Even then, we're still fucked anyways - it is impossible to form a group B now. Remember that all individual subtrees has size < a, and a < b, so forming a grpup B is now 
		impossible.
		Example: Consider the tree in this image (Geogebra is unironically good for drawing trees, woo)
		https://media.discordapp.net/attachments/1095739885492645907/1181511670212870234/image.png?ex=6581537d&is=656ede7d&hm=c24b7e25ce4fc0e64c0f81a1e864fdbf6e8f851029f9801690d887bf99d9ef80&=&format=webp&quality=lossless&width=379&height=400
		The tree has 18 vertices, with centroid A. Considering the split (6,6,6).
		There doesn't exist a subtree with size >=6 when we root the tree at centroid A, so we either have to "merge" some subtree (the one at B and the one at D) to create a suitable
		group A. Regardless, the centroid is used, and we are now unable to form a valid group B.
		(less strict and more intuitive reason why we only have to try the centroid: The strongest tests would be those with a=b=c (as the validity of a split on a tree entirely
		depends on whether a subtree with size a exists or not). The centroid is where the size of the subtrees are the most "balanced" (if a subtree with size >=a exists then there
		will always exist a valid split as there will always be > n/2 > b vertices left). Basically, just pick the only special point on a tree that is relevant in a problem
		that asks about something something subtree size, lmao. tf is tree diameter and those special properties doing in MY connected component size task?
		*/
		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++){
			IsCentroid=1;
			//Check whether this is the centroid of the DFS tree or not. Proceed if it is
			for(int l=0;l<cadj[k].size();l++){
				IsCentroid&=(GetSubtreeSize(k,l)<=N/2);
			}
			if(!IsCentroid){
				continue;
			}
			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;
				int t=1;
				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
				//Because you're wrong, dumbass. It is indeed true on a tree. However, on a general graph, funny things like in the following tree could exist
			}
		}
	}
	ans.clear();
	for(int i=0;i<N;i++){
		ans.push_back(0);
	}
	return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:88:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |  for(int i=0;i<p.size();i++){
      |              ~^~~~~~~~~
split.cpp:157:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  157 |    for(int l=0;l<cadj[k].size();l++){
      |                ~^~~~~~~~~~~~~~~
split.cpp:163:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |    for(int l=0;l<cadj[k].size();l++){
      |                ~^~~~~~~~~~~~~~~
split.cpp:178:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  178 |       for(int d=0;d<cadj[clist.front()].size();d++){
      |                   ~^~~~~~~~~~~~~~~~~~~~~~~~~~~
split.cpp:197:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  197 |       for(int d=0;d<cadj[clist.front()].size();d++){
      |                   ~^~~~~~~~~~~~~~~~~~~~~~~~~~~
split.cpp:169:9: warning: unused variable 't' [-Wunused-variable]
  169 |     int t=1;
      |         ^

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