이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
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;
}
}
}
}
}
}
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;
}
컴파일 시 표준 에러 (stderr) 메시지
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:352:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
352 | for(int st2=0;st2<tadj[clist.front()].size();st2++){
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
