답안 #890175

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
890175 2023-12-20T16:17:29 Z Lib Split the Attractions (IOI19_split) C++14
100 / 100
115 ms 36284 KB
#include <bits/stdc++.h>
#include "split.h"
using namespace std;
vector <vector <int> > adj;
vector <vector <int> > cadj;
vector <vector <int> > tadj;
vector <vector <int> > altadj; //For alternative graph G'
vector <int> TVector;
int check[300003];
int SubtreeSize[300003];
int Parent[300003];
int Check2[300003];
int Weight[300003]; //Weight of each node on graph G'
int n;
int N;
set <int> CurrentComponent;
int CurrentComponentSize;
//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?
		
		Stricter proof that "If there exists a valid split, there exists a valid split at the centroid" (On any given tree):
		We call a split "at X" if:
		- Every single vertices of group A belong to the same subtree of a children of X when we root the tree at X
		- Vertices of group B lies among the remaining vertices.
		Let the root of the subtree that contains all of group A be Y. Of course Y is adjacent to X.
		Recall the process of finding the centroid from an arbitrary vertex on any given tree:
		- We start at that point,X , and "move" X into the only subtree that has size > N/2
		- Terminates if we can no longer do that.
		Notice that: As we are moving X towards the centroid (assuming that a valid split at X exists), the validity of the split doesn't change:
		- The subtree that contains group A will constantly get larger => Valid assignment for group A still exists
		- The "this doesn't belong to group A" subtree will still allow a valid assignment for group B to exist:
		+ Do remember that the upper bound for the size of group B is N/2.
		+ If the process of moving towards the centroid hasn't ended, there exists a subtree with size > N/2 >= B. Just dedicate this entire subtree to group B
		=> By trying to find the centroid from X (and move Y along), we can divide the tree into 2 zones such that a valid split still exists, after each step. This
		process ends when X becomes the centroid => ...there's that. there exists a valid split at the centroid.
		*/
		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;
			}
			altadj.push_back(TVector);
			for(int l=0;l<cadj[k].size();l++){
				altadj.push_back(TVector);
				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
				/*
				(the following shitfucking is aimed towards myself and not you, reader.)
				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. Just look at this graph
				https://cdn.discordapp.com/attachments/1095739885492645907/1181516710092742676/image.png?ex=6581582f&is=656ee32f&hm=2130ffcfecd98766c518f44d32dc29f092be526571fb053a31e059ed1004d940&
				(It is still the same tree from above, but with some edges added in. The blue edges is the DFS spanning tree. The red edges are the ones not in the spanning tree.)
				Let's consider the split (6,6,6) once again. This shouldn't be possible if we only consider dedicating exactly 1 subtree to group A - reasons already explained above. However,
				it is trivial to see that a valid split indeed does exist - (D,I,J,K,L,E) to group A, (B,H,F,G,O,Q) to group B, and the rest to group C. Why tf is this possible?
				It is possible because, since this is a graph we're talking about, there could (potentially) exist edges that connects between different subtrees. With these edges, we can
				merge these subtrees together WITHOUT even having to use the centroid.
				So, how do we deal with this now? It is simple. Build a new graph G'. Assuming that we have k different subtrees, the ith of those have C[i] vertices, we will "turn" each of these
				subtrees into corresponding vertices in the new graph G'. The ith node in G', which corresponds to the ith subtree, will have weight C[i]. If there exists an edge that connects
				between a vertex in the ith subtree and a vertex in the jth subtree in the original graph, we create an edge between node i and j in graph G'. Now, the task transforms from
				"Find a group of A vertices that belongs in the same connected component by merging some subtrees in graph G (the original)" into "Find  a connected component with weight>=A 
				in graph G'". How do you do that? The exact fucking thing you did for subtask 3.
				(Graph G' will look something like this btw: https://cdn.discordapp.com/attachments/1095739885492645907/1181524161823252512/image.png?ex=65815f1f&is=656eea1f&hm=1c0cba1ed84b7f57e88c0224881a8ac66117db8b9bfd0c94a8f9d4966358d584&)
				
				Even funnier: After you realize you can turn this from an unweighted version in graph G into a weighted variant in graph G', you can just go ahead and implement it and literally
				proof by AC. THe answer literally body-slams you in the face - doing this thing that seems correct, is indeed, the correct thing to do.
				
				Observation: If there exists a connected component in graph G' with total weight >=a, there exists a valid split in graph G.
				Proof: We do the same thing we did for subtask 3. Instead of merging single. unweighted vertices in graph G, we're merging weighted vertices in graph G' now. We do the same thing for
				subtask 3 - trying to find a valid connected component by BFS/DFS something something. When we "merge" 1 component at a time by BFS/DFS, the following happens:
				- The size of the component that's currently considered increases. There doesn't exist a component with size <1
				- With each merge, the size of the component increases by NO MORE THAN A - if there exists a "vertices" on graph G' with weight > a, this means a subtree with size >a
				exists in the original graph G. We would've considered this subtree and made a valid assignment already - the algorithm wouldn't even get to this Phase 2. Which means:
				- Just by constantly merging, there either doesn't exist any component with weight >=a in graph G'  at all (which means no valid split exists in graph G), or we are 
				guaranteed to find a component with size >=a and <2a. (we are increasing by less than a after each merge, and (something less than a)+ (something less than a) would
				always be <2a (....If you do notice, this is literally how the full solution to Detecting Molecules from IOI 2016 works)
				- If we do find a component with size >=a and <= 2a, there exists a way to merge the remaining subtrees so that a connected component with size B (in graph G) exists.
				Do recall that: All subtrees are still connected with eachother (in graph G) through the centroid. The size of the "merged subtree component" is less than 2a,
				so if we "cut" this merged component out of the original tree, the remaining connected component of subtrees connected with eachother through the centroid
				would have size > N-2a > N-a-c = b. Which means that: By merging the subtrees with eachother one by one (through the form of BFS/DFS in the alternative graph G'),
				we are guaranteed to find a valid split if it exists.
				
				The rest is just implementing 3 BFS/DFS and forming a secondary graph, which is a pain in the ass
				*/
			}
			for(int l=0;l<N;l++){
				check[l]=0;
			}
			check[k]=-1;
			//Marking the points to determine which subtree it belongs to
			clist.clear();
			for(int l=0;l<cadj[k].size();l++){
			check[cadj[k][l]]=l+1;
			Weight[l+1]=GetSubtreeSize(k,l);
			clist.push_back(cadj[k][l]);
			}
			while(!clist.empty()){
				for(int l=0;l<cadj[clist.front()].size();l++){
					if(!check[cadj[clist.front()][l]]){
						check[cadj[clist.front()][l]]=check[clist.front()];
						clist.push_back(cadj[clist.front()][l]);
					}
				}
				clist.pop_front();
			}
			//Generate graph G'
			for(int l=0;l<p.size();l++){
				if(check[p[l]]!=check[q[l]]&&p[l]!=k&&q[l]!=k){
					altadj[check[p[l]]].push_back(check[q[l]]);
					altadj[check[q[l]]].push_back(check[p[l]]);
				}
			}
			//BFS on graph G'. Keeping track of the vertices on graph G' (set of subtrees on graph G). Yeet them into a set.
			//Set isn't needed but I'm done with this shit. Exist for easier marking. Who needs to do it in O(N) when N<=1e5 anyways
			for(int l=1;l<=altadj.size();l++){
				if(!Check2[l]){
					CurrentComponent.clear();
					CurrentComponentSize=0;
					clist.clear();
					clist.push_back(l);
					CurrentComponent.insert(l);
					CurrentComponentSize+=Weight[l];
					Check2[l]=1;
					while(!clist.empty()){
						for(int m=0;m<altadj[l].size();m++){
							if(!Check2[altadj[l][m]]){
								CurrentComponent.insert(altadj[l][m]);
								Check2[altadj[l][m]]=1;
								CurrentComponentSize+=Weight[altadj[l][m]];
								if(CurrentComponentSize>=GroupASize){
									//WOAHHHHHHHHHHHHHHH FOUND A VALID SPLIT. INITIATE MASS MARKING
									CurrentComponentSize=1;
									for(int st=0;st<n;st++){
										Check2[st]=0;
									}
									//BFS on the current component. Mark exactly a vertices in this component with the ID of group A
									while(!clist.empty()){
                                      clist.pop_back();
                                    }
									for(int st=0;st<n;st++){
										if(CurrentComponent.count(check[st])){
											clist.push_back(st);
											Check2[st]=GroupAID;
											while(!clist.empty()){
												for(int st2=0;st2<tadj[clist.front()].size();st2++){
													//Only mark this if it belongs to the currently considered subtrees
													if(!Check2[tadj[clist.front()][st2]]&&CurrentComponent.count(check[tadj[clist.front()][st2]])){
														clist.push_back(tadj[clist.front()][st2]);
														Check2[tadj[clist.front()][st2]]=GroupAID;
														CurrentComponentSize++;
														if(CurrentComponentSize==GroupASize){
															//Move on to marking group B
															goto MarkGroupB;
														}
													}
												}
												clist.pop_front();
											}
										}
									}
									MarkGroupB:
									while(!clist.empty()){
                                      clist.pop_back();
                                    }
									CurrentComponentSize=1;
									//error probably because centroid is blocked or sum shit.
									for(int st=1;st<n;st++){
										if(!CurrentComponent.count(st)){
											check[k]=st;
											break;
										}
									}
									for(int st=0;st<n;st++){
										if(!CurrentComponent.count(check[st])){
											clist.push_back(st);
											Check2[st]=GroupBID;
											while(!clist.empty()){
												for(int st2=0;st2<tadj[clist.front()].size();st2++){
													//Only mark this if it DOESN'T belong to the subtrees that contains vertices of group A. As proven above, we could always
													//find a valid component B
													if(!Check2[tadj[clist.front()][st2]]&&!CurrentComponent.count(check[tadj[clist.front()][st2]])){
														clist.push_back(tadj[clist.front()][st2]);
														Check2[tadj[clist.front()][st2]]=GroupBID;
														CurrentComponentSize++;
														if(CurrentComponentSize==GroupBSize){
															//Move on to marking group C and return the answer
															goto MarkGroupC;
														}
													}
												}
												//bruh
												//someone forgot to pop_front :wheeze:
												//what the fuck
												clist.pop_front();
											}
										}
									}
									MarkGroupC:
									for(int st=0;st<n;st++){
										if(!Check2[st]){
											Check2[st]=6-GroupAID-GroupBID;
										}
										ans.push_back(Check2[st]);
									}
									return ans;
								}
								//If this component is not big enough (size < amount of vertices in group A), we simply discard this component
							}
						}
						clist.pop_front();
					}
				}
			}
		}
	}
	//If even after that 150-line triple BFS madness and we still can't find a valid split, it is not possible.
	ans.clear();
	for(int i=0;i<N;i++){
		ans.push_back(0);
	}
	return ans;
}
/*
Post AC comments:
- Cool problem. Not necessarily hard. Tying the entire proof of the "if there exists a component with size >=a in graph G', there will exist a valid split" to essentially
the easiest IOI task ever is......really cool.
- The proof of "If there exists a valid split, there exists a valid split at the centroid" is literally just replicating the process of finding centroid from
a random given node on the tree. Very funny. (it's not "intuitively" but provable btw, boutta change the proof part a little bit)
- Difficulty (idea) : 5/10. After the tree subtasks, it is obvious that some tomfoolery could be done with remaining edges that connects between 2 subtrees
(just consider the following test:
6 6
2 2 2
1 2
1 3
1 4
1 5
1 6
2 6
lol. Literally blatantly obvious.)
- Implementation difficulty: 7/10. What the fuck. Never doing 5 BFS again. Imagine 10 wrong submissions because of the funny pop_back(), lol.
(again, that's why vector is superior to stacks/queue/deque, I guess). IMO after finding out a valid split exists, having to implement the marking is a massive
pain in the ass. Literal torture. Took me 45 minutes to code the triple marking BFS, then an additional 2 hours (on total) to debug.
Maybe doing something like "Find the amount of trios (a,b,c) such that a<=b<=c and a+b+c=n and a valid split with size (a,b,c) exists" would be cooler? No painful 
shitty ass marking required (definitely not spoiler for a potential problem I will set *somewhere*, haha)
ok, updating the proof now. brb
*/

Compilation message

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:93:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |  for(int i=0;i<p.size();i++){
      |              ~^~~~~~~~~
split.cpp:178:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  178 |    for(int l=0;l<cadj[k].size();l++){
      |                ~^~~~~~~~~~~~~~~
split.cpp:185:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  185 |    for(int l=0;l<cadj[k].size();l++){
      |                ~^~~~~~~~~~~~~~~
split.cpp:201:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  201 |       for(int d=0;d<cadj[clist.front()].size();d++){
      |                   ~^~~~~~~~~~~~~~~~~~~~~~~~~~~
split.cpp:220:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  220 |       for(int d=0;d<cadj[clist.front()].size();d++){
      |                   ~^~~~~~~~~~~~~~~~~~~~~~~~~~~
split.cpp:192:9: warning: unused variable 't' [-Wunused-variable]
  192 |     int t=1;
      |         ^
split.cpp:289:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  289 |    for(int l=0;l<cadj[k].size();l++){
      |                ~^~~~~~~~~~~~~~~
split.cpp:295:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  295 |     for(int l=0;l<cadj[clist.front()].size();l++){
      |                 ~^~~~~~~~~~~~~~~~~~~~~~~~~~~
split.cpp:304:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  304 |    for(int l=0;l<p.size();l++){
      |                ~^~~~~~~~~
split.cpp:312:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  312 |    for(int l=1;l<=altadj.size();l++){
      |                ~^~~~~~~~~~~~~~~
split.cpp:322:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  322 |       for(int m=0;m<altadj[l].size();m++){
      |                   ~^~~~~~~~~~~~~~~~~
split.cpp:342:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  342 |             for(int st2=0;st2<tadj[clist.front()].size();st2++){
      |                           ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
split.cpp:375:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  375 |             for(int st2=0;st2<tadj[clist.front()].size();st2++){
      |                           ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB ok, correct split
2 Correct 1 ms 2396 KB ok, correct split
3 Correct 1 ms 2396 KB ok, correct split
4 Correct 1 ms 2396 KB ok, correct split
5 Correct 1 ms 2396 KB ok, correct split
6 Correct 1 ms 2396 KB ok, correct split
7 Correct 64 ms 22992 KB ok, correct split
8 Correct 62 ms 23160 KB ok, correct split
9 Correct 69 ms 22940 KB ok, correct split
10 Correct 61 ms 22824 KB ok, correct split
11 Correct 63 ms 23344 KB ok, correct split
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB ok, correct split
2 Correct 1 ms 2396 KB ok, correct split
3 Correct 1 ms 2396 KB ok, correct split
4 Correct 75 ms 24380 KB ok, correct split
5 Correct 72 ms 22772 KB ok, correct split
6 Correct 62 ms 22804 KB ok, correct split
7 Correct 62 ms 23512 KB ok, correct split
8 Correct 86 ms 25152 KB ok, correct split
9 Correct 62 ms 22332 KB ok, correct split
10 Correct 56 ms 24136 KB ok, correct split
11 Correct 94 ms 24076 KB ok, correct split
12 Correct 59 ms 24460 KB ok, correct split
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB ok, correct split
2 Correct 68 ms 23220 KB ok, correct split
3 Correct 35 ms 10764 KB ok, correct split
4 Correct 1 ms 2396 KB ok, correct split
5 Correct 78 ms 23104 KB ok, correct split
6 Correct 77 ms 22912 KB ok, correct split
7 Correct 68 ms 22880 KB ok, correct split
8 Correct 87 ms 22756 KB ok, correct split
9 Correct 79 ms 22856 KB ok, correct split
10 Correct 22 ms 9372 KB ok, no valid answer
11 Correct 30 ms 12852 KB ok, no valid answer
12 Correct 85 ms 27460 KB ok, no valid answer
13 Correct 74 ms 24000 KB ok, no valid answer
14 Correct 76 ms 29724 KB ok, no valid answer
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB ok, correct split
2 Correct 1 ms 2396 KB ok, no valid answer
3 Correct 1 ms 2396 KB ok, correct split
4 Correct 1 ms 2396 KB ok, correct split
5 Correct 1 ms 2396 KB ok, correct split
6 Correct 1 ms 2396 KB ok, correct split
7 Correct 1 ms 2392 KB ok, correct split
8 Correct 1 ms 2396 KB ok, correct split
9 Correct 2 ms 3160 KB ok, correct split
10 Correct 2 ms 3016 KB ok, correct split
11 Correct 1 ms 2396 KB ok, correct split
12 Correct 2 ms 2908 KB ok, correct split
13 Correct 1 ms 2392 KB ok, correct split
14 Correct 1 ms 2492 KB ok, correct split
15 Correct 1 ms 2392 KB ok, correct split
16 Correct 1 ms 2396 KB ok, correct split
17 Correct 1 ms 2652 KB ok, correct split
18 Correct 2 ms 2396 KB ok, correct split
19 Correct 1 ms 2392 KB ok, correct split
20 Correct 4 ms 2648 KB ok, correct split
21 Correct 2 ms 2908 KB ok, correct split
22 Correct 2 ms 2908 KB ok, correct split
23 Correct 2 ms 2908 KB ok, correct split
24 Correct 2 ms 2908 KB ok, correct split
25 Correct 3 ms 2908 KB ok, correct split
26 Correct 4 ms 3164 KB ok, correct split
27 Correct 3 ms 3164 KB ok, correct split
28 Correct 3 ms 3288 KB ok, correct split
29 Correct 1 ms 2396 KB ok, correct split
30 Correct 3 ms 3020 KB ok, correct split
31 Correct 1 ms 2396 KB ok, correct split
32 Correct 1 ms 2396 KB ok, correct split
33 Correct 1 ms 2400 KB ok, correct split
34 Correct 3 ms 2912 KB ok, correct split
35 Correct 2 ms 2908 KB ok, correct split
36 Correct 2 ms 2908 KB ok, correct split
37 Correct 3 ms 2908 KB ok, correct split
38 Correct 3 ms 2908 KB ok, correct split
39 Correct 3 ms 3084 KB ok, correct split
40 Correct 2 ms 2908 KB ok, correct split
41 Correct 2 ms 2656 KB ok, correct split
42 Correct 2 ms 2652 KB ok, correct split
43 Correct 4 ms 2908 KB ok, correct split
44 Correct 2 ms 3160 KB ok, correct split
45 Correct 2 ms 3168 KB ok, correct split
46 Correct 2 ms 2908 KB ok, correct split
47 Correct 3 ms 2904 KB ok, no valid answer
48 Correct 2 ms 2792 KB ok, correct split
49 Correct 2 ms 2912 KB ok, correct split
50 Correct 1 ms 2516 KB ok, no valid answer
51 Correct 1 ms 2392 KB ok, no valid answer
52 Correct 2 ms 3012 KB ok, no valid answer
53 Correct 2 ms 2904 KB ok, no valid answer
54 Correct 2 ms 3164 KB ok, no valid answer
55 Correct 2 ms 2908 KB ok, no valid answer
56 Correct 2 ms 2908 KB ok, no valid answer
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB ok, correct split
2 Correct 1 ms 2396 KB ok, correct split
3 Correct 1 ms 2396 KB ok, correct split
4 Correct 1 ms 2396 KB ok, correct split
5 Correct 1 ms 2396 KB ok, correct split
6 Correct 1 ms 2396 KB ok, correct split
7 Correct 64 ms 22992 KB ok, correct split
8 Correct 62 ms 23160 KB ok, correct split
9 Correct 69 ms 22940 KB ok, correct split
10 Correct 61 ms 22824 KB ok, correct split
11 Correct 63 ms 23344 KB ok, correct split
12 Correct 1 ms 2396 KB ok, correct split
13 Correct 1 ms 2396 KB ok, correct split
14 Correct 1 ms 2396 KB ok, correct split
15 Correct 75 ms 24380 KB ok, correct split
16 Correct 72 ms 22772 KB ok, correct split
17 Correct 62 ms 22804 KB ok, correct split
18 Correct 62 ms 23512 KB ok, correct split
19 Correct 86 ms 25152 KB ok, correct split
20 Correct 62 ms 22332 KB ok, correct split
21 Correct 56 ms 24136 KB ok, correct split
22 Correct 94 ms 24076 KB ok, correct split
23 Correct 59 ms 24460 KB ok, correct split
24 Correct 1 ms 2392 KB ok, correct split
25 Correct 68 ms 23220 KB ok, correct split
26 Correct 35 ms 10764 KB ok, correct split
27 Correct 1 ms 2396 KB ok, correct split
28 Correct 78 ms 23104 KB ok, correct split
29 Correct 77 ms 22912 KB ok, correct split
30 Correct 68 ms 22880 KB ok, correct split
31 Correct 87 ms 22756 KB ok, correct split
32 Correct 79 ms 22856 KB ok, correct split
33 Correct 22 ms 9372 KB ok, no valid answer
34 Correct 30 ms 12852 KB ok, no valid answer
35 Correct 85 ms 27460 KB ok, no valid answer
36 Correct 74 ms 24000 KB ok, no valid answer
37 Correct 76 ms 29724 KB ok, no valid answer
38 Correct 1 ms 2396 KB ok, correct split
39 Correct 1 ms 2396 KB ok, no valid answer
40 Correct 1 ms 2396 KB ok, correct split
41 Correct 1 ms 2396 KB ok, correct split
42 Correct 1 ms 2396 KB ok, correct split
43 Correct 1 ms 2396 KB ok, correct split
44 Correct 1 ms 2392 KB ok, correct split
45 Correct 1 ms 2396 KB ok, correct split
46 Correct 2 ms 3160 KB ok, correct split
47 Correct 2 ms 3016 KB ok, correct split
48 Correct 1 ms 2396 KB ok, correct split
49 Correct 2 ms 2908 KB ok, correct split
50 Correct 1 ms 2392 KB ok, correct split
51 Correct 1 ms 2492 KB ok, correct split
52 Correct 1 ms 2392 KB ok, correct split
53 Correct 1 ms 2396 KB ok, correct split
54 Correct 1 ms 2652 KB ok, correct split
55 Correct 2 ms 2396 KB ok, correct split
56 Correct 1 ms 2392 KB ok, correct split
57 Correct 4 ms 2648 KB ok, correct split
58 Correct 2 ms 2908 KB ok, correct split
59 Correct 2 ms 2908 KB ok, correct split
60 Correct 2 ms 2908 KB ok, correct split
61 Correct 2 ms 2908 KB ok, correct split
62 Correct 3 ms 2908 KB ok, correct split
63 Correct 4 ms 3164 KB ok, correct split
64 Correct 3 ms 3164 KB ok, correct split
65 Correct 3 ms 3288 KB ok, correct split
66 Correct 1 ms 2396 KB ok, correct split
67 Correct 3 ms 3020 KB ok, correct split
68 Correct 1 ms 2396 KB ok, correct split
69 Correct 1 ms 2396 KB ok, correct split
70 Correct 1 ms 2400 KB ok, correct split
71 Correct 3 ms 2912 KB ok, correct split
72 Correct 2 ms 2908 KB ok, correct split
73 Correct 2 ms 2908 KB ok, correct split
74 Correct 3 ms 2908 KB ok, correct split
75 Correct 3 ms 2908 KB ok, correct split
76 Correct 3 ms 3084 KB ok, correct split
77 Correct 2 ms 2908 KB ok, correct split
78 Correct 2 ms 2656 KB ok, correct split
79 Correct 2 ms 2652 KB ok, correct split
80 Correct 4 ms 2908 KB ok, correct split
81 Correct 2 ms 3160 KB ok, correct split
82 Correct 2 ms 3168 KB ok, correct split
83 Correct 2 ms 2908 KB ok, correct split
84 Correct 3 ms 2904 KB ok, no valid answer
85 Correct 2 ms 2792 KB ok, correct split
86 Correct 2 ms 2912 KB ok, correct split
87 Correct 1 ms 2516 KB ok, no valid answer
88 Correct 1 ms 2392 KB ok, no valid answer
89 Correct 2 ms 3012 KB ok, no valid answer
90 Correct 2 ms 2904 KB ok, no valid answer
91 Correct 2 ms 3164 KB ok, no valid answer
92 Correct 2 ms 2908 KB ok, no valid answer
93 Correct 2 ms 2908 KB ok, no valid answer
94 Correct 68 ms 23448 KB ok, correct split
95 Correct 86 ms 25816 KB ok, correct split
96 Correct 80 ms 25172 KB ok, correct split
97 Correct 23 ms 10828 KB ok, correct split
98 Correct 27 ms 10892 KB ok, correct split
99 Correct 44 ms 11100 KB ok, correct split
100 Correct 83 ms 25924 KB ok, correct split
101 Correct 78 ms 25172 KB ok, correct split
102 Correct 80 ms 25680 KB ok, correct split
103 Correct 71 ms 24960 KB ok, correct split
104 Correct 79 ms 26948 KB ok, correct split
105 Correct 49 ms 15808 KB ok, correct split
106 Correct 115 ms 36284 KB ok, correct split
107 Correct 73 ms 23880 KB ok, correct split
108 Correct 71 ms 23876 KB ok, correct split
109 Correct 100 ms 26232 KB ok, correct split
110 Correct 100 ms 27416 KB ok, correct split
111 Correct 94 ms 27708 KB ok, correct split
112 Correct 109 ms 27324 KB ok, correct split
113 Correct 98 ms 28228 KB ok, correct split
114 Correct 9 ms 4960 KB ok, correct split
115 Correct 8 ms 4908 KB ok, correct split
116 Correct 89 ms 27716 KB ok, correct split
117 Correct 88 ms 26680 KB ok, correct split
118 Correct 59 ms 22600 KB ok, correct split
119 Correct 65 ms 23128 KB ok, correct split
120 Correct 60 ms 22592 KB ok, correct split
121 Correct 64 ms 22872 KB ok, no valid answer
122 Correct 68 ms 23876 KB ok, no valid answer
123 Correct 89 ms 25928 KB ok, no valid answer
124 Correct 109 ms 26420 KB ok, no valid answer
125 Correct 78 ms 29608 KB ok, no valid answer
126 Correct 55 ms 28356 KB ok, no valid answer
127 Correct 74 ms 29144 KB ok, no valid answer