#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++){
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
