oj.uz

답안 #890152

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
890152 2023-12-20T15:51:19 Z Lib Split the Attractions (IOI19_split) C++14
100 / 100
 114 ms 37308 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?
		*/
		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;
}

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:162:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  162 |    for(int l=0;l<cadj[k].size();l++){
      |                ~^~~~~~~~~~~~~~~
split.cpp:169:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  169 |    for(int l=0;l<cadj[k].size();l++){
      |                ~^~~~~~~~~~~~~~~
split.cpp:185:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  185 |       for(int d=0;d<cadj[clist.front()].size();d++){
      |                   ~^~~~~~~~~~~~~~~~~~~~~~~~~~~
split.cpp:204:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  204 |       for(int d=0;d<cadj[clist.front()].size();d++){
      |                   ~^~~~~~~~~~~~~~~~~~~~~~~~~~~
split.cpp:176:9: warning: unused variable 't' [-Wunused-variable]
  176 |     int t=1;
      |         ^
split.cpp:273:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  273 |    for(int l=0;l<cadj[k].size();l++){
      |                ~^~~~~~~~~~~~~~~
split.cpp:279:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  279 |     for(int l=0;l<cadj[clist.front()].size();l++){
      |                 ~^~~~~~~~~~~~~~~~~~~~~~~~~~~
split.cpp:288:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  288 |    for(int l=0;l<p.size();l++){
      |                ~^~~~~~~~~
split.cpp:296:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  296 |    for(int l=1;l<=altadj.size();l++){
      |                ~^~~~~~~~~~~~~~~
split.cpp:306:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  306 |       for(int m=0;m<altadj[l].size();m++){
      |                   ~^~~~~~~~~~~~~~~~~
split.cpp:326:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  326 |             for(int st2=0;st2<tadj[clist.front()].size();st2++){
      |                           ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
split.cpp:359:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  359 |             for(int st2=0;st2<tadj[clist.front()].size();st2++){
      |                           ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB ok, correct split
2 Correct 1 ms 2396 KB ok, correct split
3 Correct 0 ms 2396 KB ok, correct split
4 Correct 1 ms 2396 KB ok, correct split
5 Correct 1 ms 2392 KB ok, correct split
6 Correct 1 ms 2396 KB ok, correct split
7 Correct 60 ms 22160 KB ok, correct split
8 Correct 64 ms 21812 KB ok, correct split
9 Correct 59 ms 21832 KB ok, correct split
10 Correct 62 ms 22084 KB ok, correct split
11 Correct 81 ms 22336 KB ok, correct split

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB ok, correct split
2 Correct 0 ms 2396 KB ok, correct split
3 Correct 1 ms 2396 KB ok, correct split
4 Correct 73 ms 23356 KB ok, correct split
5 Correct 67 ms 22084 KB ok, correct split
6 Correct 59 ms 22592 KB ok, correct split
7 Correct 62 ms 22084 KB ok, correct split
8 Correct 81 ms 24124 KB ok, correct split
9 Correct 82 ms 21792 KB ok, correct split
10 Correct 52 ms 23888 KB ok, correct split
11 Correct 52 ms 23620 KB ok, correct split
12 Correct 56 ms 23620 KB ok, correct split

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB ok, correct split
2 Correct 71 ms 22540 KB ok, correct split
3 Correct 27 ms 10416 KB ok, correct split
4 Correct 1 ms 2396 KB ok, correct split
5 Correct 68 ms 21832 KB ok, correct split
6 Correct 58 ms 21832 KB ok, correct split
7 Correct 63 ms 22088 KB ok, correct split
8 Correct 61 ms 22340 KB ok, correct split
9 Correct 64 ms 21828 KB ok, correct split
10 Correct 20 ms 9048 KB ok, no valid answer
11 Correct 29 ms 12376 KB ok, no valid answer
12 Correct 67 ms 26848 KB ok, no valid answer
13 Correct 66 ms 23628 KB ok, no valid answer
14 Correct 66 ms 28096 KB ok, no valid answer

Subtask #4
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB ok, correct split
2 Correct 0 ms 2396 KB ok, no valid answer
3 Correct 0 ms 2396 KB ok, correct split
4 Correct 0 ms 2396 KB ok, correct split
5 Correct 1 ms 2408 KB ok, correct split
6 Correct 1 ms 2396 KB ok, correct split
7 Correct 1 ms 2396 KB ok, correct split
8 Correct 1 ms 2396 KB ok, correct split
9 Correct 2 ms 2908 KB ok, correct split
10 Correct 2 ms 2908 KB ok, correct split
11 Correct 1 ms 2396 KB ok, correct split
12 Correct 2 ms 2904 KB ok, correct split
13 Correct 1 ms 2396 KB ok, correct split
14 Correct 1 ms 2396 KB ok, correct split
15 Correct 1 ms 2396 KB ok, correct split
16 Correct 1 ms 2396 KB ok, correct split
17 Correct 1 ms 2396 KB ok, correct split
18 Correct 1 ms 2396 KB ok, correct split
19 Correct 1 ms 2392 KB ok, correct split
20 Correct 1 ms 2652 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 3164 KB ok, correct split
24 Correct 2 ms 2908 KB ok, correct split
25 Correct 2 ms 2908 KB ok, correct split
26 Correct 2 ms 3164 KB ok, correct split
27 Correct 3 ms 3164 KB ok, correct split
28 Correct 3 ms 3164 KB ok, correct split
29 Correct 1 ms 2396 KB ok, correct split
30 Correct 2 ms 2908 KB ok, correct split
31 Correct 1 ms 2396 KB ok, correct split
32 Correct 1 ms 2564 KB ok, correct split
33 Correct 1 ms 2396 KB ok, correct split
34 Correct 2 ms 2908 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 3020 KB ok, correct split
38 Correct 3 ms 3164 KB ok, correct split
39 Correct 3 ms 3164 KB ok, correct split
40 Correct 2 ms 2908 KB ok, correct split
41 Correct 1 ms 2652 KB ok, correct split
42 Correct 2 ms 2648 KB ok, correct split
43 Correct 2 ms 3164 KB ok, correct split
44 Correct 3 ms 3164 KB ok, correct split
45 Correct 2 ms 2908 KB ok, correct split
46 Correct 2 ms 2908 KB ok, correct split
47 Correct 2 ms 2908 KB ok, no valid answer
48 Correct 2 ms 2908 KB ok, correct split
49 Correct 2 ms 2908 KB ok, correct split
50 Correct 1 ms 2396 KB ok, no valid answer
51 Correct 1 ms 2396 KB ok, no valid answer
52 Correct 2 ms 3044 KB ok, no valid answer
53 Correct 2 ms 2908 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 3 ms 2908 KB ok, no valid answer

Subtask #5
36.0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB ok, correct split
2 Correct 1 ms 2396 KB ok, correct split
3 Correct 0 ms 2396 KB ok, correct split
4 Correct 1 ms 2396 KB ok, correct split
5 Correct 1 ms 2392 KB ok, correct split
6 Correct 1 ms 2396 KB ok, correct split
7 Correct 60 ms 22160 KB ok, correct split
8 Correct 64 ms 21812 KB ok, correct split
9 Correct 59 ms 21832 KB ok, correct split
10 Correct 62 ms 22084 KB ok, correct split
11 Correct 81 ms 22336 KB ok, correct split
12 Correct 1 ms 2396 KB ok, correct split
13 Correct 0 ms 2396 KB ok, correct split
14 Correct 1 ms 2396 KB ok, correct split
15 Correct 73 ms 23356 KB ok, correct split
16 Correct 67 ms 22084 KB ok, correct split
17 Correct 59 ms 22592 KB ok, correct split
18 Correct 62 ms 22084 KB ok, correct split
19 Correct 81 ms 24124 KB ok, correct split
20 Correct 82 ms 21792 KB ok, correct split
21 Correct 52 ms 23888 KB ok, correct split
22 Correct 52 ms 23620 KB ok, correct split
23 Correct 56 ms 23620 KB ok, correct split
24 Correct 1 ms 2396 KB ok, correct split
25 Correct 71 ms 22540 KB ok, correct split
26 Correct 27 ms 10416 KB ok, correct split
27 Correct 1 ms 2396 KB ok, correct split
28 Correct 68 ms 21832 KB ok, correct split
29 Correct 58 ms 21832 KB ok, correct split
30 Correct 63 ms 22088 KB ok, correct split
31 Correct 61 ms 22340 KB ok, correct split
32 Correct 64 ms 21828 KB ok, correct split
33 Correct 20 ms 9048 KB ok, no valid answer
34 Correct 29 ms 12376 KB ok, no valid answer
35 Correct 67 ms 26848 KB ok, no valid answer
36 Correct 66 ms 23628 KB ok, no valid answer
37 Correct 66 ms 28096 KB ok, no valid answer
38 Correct 1 ms 2396 KB ok, correct split
39 Correct 0 ms 2396 KB ok, no valid answer
40 Correct 0 ms 2396 KB ok, correct split
41 Correct 0 ms 2396 KB ok, correct split
42 Correct 1 ms 2408 KB ok, correct split
43 Correct 1 ms 2396 KB ok, correct split
44 Correct 1 ms 2396 KB ok, correct split
45 Correct 1 ms 2396 KB ok, correct split
46 Correct 2 ms 2908 KB ok, correct split
47 Correct 2 ms 2908 KB ok, correct split
48 Correct 1 ms 2396 KB ok, correct split
49 Correct 2 ms 2904 KB ok, correct split
50 Correct 1 ms 2396 KB ok, correct split
51 Correct 1 ms 2396 KB ok, correct split
52 Correct 1 ms 2396 KB ok, correct split
53 Correct 1 ms 2396 KB ok, correct split
54 Correct 1 ms 2396 KB ok, correct split
55 Correct 1 ms 2396 KB ok, correct split
56 Correct 1 ms 2392 KB ok, correct split
57 Correct 1 ms 2652 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 3164 KB ok, correct split
61 Correct 2 ms 2908 KB ok, correct split
62 Correct 2 ms 2908 KB ok, correct split
63 Correct 2 ms 3164 KB ok, correct split
64 Correct 3 ms 3164 KB ok, correct split
65 Correct 3 ms 3164 KB ok, correct split
66 Correct 1 ms 2396 KB ok, correct split
67 Correct 2 ms 2908 KB ok, correct split
68 Correct 1 ms 2396 KB ok, correct split
69 Correct 1 ms 2564 KB ok, correct split
70 Correct 1 ms 2396 KB ok, correct split
71 Correct 2 ms 2908 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 3020 KB ok, correct split
75 Correct 3 ms 3164 KB ok, correct split
76 Correct 3 ms 3164 KB ok, correct split
77 Correct 2 ms 2908 KB ok, correct split
78 Correct 1 ms 2652 KB ok, correct split
79 Correct 2 ms 2648 KB ok, correct split
80 Correct 2 ms 3164 KB ok, correct split
81 Correct 3 ms 3164 KB ok, correct split
82 Correct 2 ms 2908 KB ok, correct split
83 Correct 2 ms 2908 KB ok, correct split
84 Correct 2 ms 2908 KB ok, no valid answer
85 Correct 2 ms 2908 KB ok, correct split
86 Correct 2 ms 2908 KB ok, correct split
87 Correct 1 ms 2396 KB ok, no valid answer
88 Correct 1 ms 2396 KB ok, no valid answer
89 Correct 2 ms 3044 KB ok, no valid answer
90 Correct 2 ms 2908 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 3 ms 2908 KB ok, no valid answer
94 Correct 75 ms 23656 KB ok, correct split
95 Correct 86 ms 26368 KB ok, correct split
96 Correct 80 ms 25336 KB ok, correct split
97 Correct 23 ms 10832 KB ok, correct split
98 Correct 24 ms 10836 KB ok, correct split
99 Correct 32 ms 11348 KB ok, correct split
100 Correct 86 ms 26684 KB ok, correct split
101 Correct 76 ms 25932 KB ok, correct split
102 Correct 79 ms 26184 KB ok, correct split
103 Correct 70 ms 25608 KB ok, correct split
104 Correct 81 ms 27976 KB ok, correct split
105 Correct 49 ms 15748 KB ok, correct split
106 Correct 114 ms 37308 KB ok, correct split
107 Correct 68 ms 23724 KB ok, correct split
108 Correct 74 ms 23868 KB ok, correct split
109 Correct 104 ms 26844 KB ok, correct split
110 Correct 107 ms 28888 KB ok, correct split
111 Correct 94 ms 28740 KB ok, correct split
112 Correct 95 ms 27304 KB ok, correct split
113 Correct 102 ms 28488 KB ok, correct split
114 Correct 9 ms 4960 KB ok, correct split
115 Correct 8 ms 4956 KB ok, correct split
116 Correct 91 ms 28532 KB ok, correct split
117 Correct 93 ms 28044 KB ok, correct split
118 Correct 66 ms 22876 KB ok, correct split
119 Correct 59 ms 23368 KB ok, correct split
120 Correct 58 ms 23872 KB ok, correct split
121 Correct 87 ms 22944 KB ok, no valid answer
122 Correct 71 ms 24772 KB ok, no valid answer
123 Correct 108 ms 26972 KB ok, no valid answer
124 Correct 85 ms 27200 KB ok, no valid answer
125 Correct 83 ms 30616 KB ok, no valid answer
126 Correct 58 ms 27848 KB ok, no valid answer
127 Correct 97 ms 29624 KB ok, no valid answer