Submission #545831

#	Time	Username	Problem	Language	Result	Execution time	Memory
545831		HappyPacMan	Split the Attractions (IOI19_split)	C++14	100 / 100	147 ms	33672 KiB

split

#include "split.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 2;
vector<pair<int,int> > color;
vector<int> adj[maxn],adjTree[maxn],sack[maxn],res;
bool vis[maxn];
int N,M,A,B,C,subSize[maxn],par[maxn],centroid;

void dfsTree(int u){
    bool isCentroid = true;
    vis[u] = true;
    subSize[u] = 1;
    for(int v : adj[u]){
        if(!vis[v]){
            dfsTree(v);
            subSize[u] += subSize[v];
            if(subSize[v] > N/2){
                isCentroid = false;
            }
            adjTree[u].push_back(v);
            adjTree[v].push_back(u);
        }
    }
    if(isCentroid && N-subSize[u] <= N/2){
        centroid = u;
    }
}
void dfsLow(int u,int c){
    if(A == 0) return;
    res[u] = c;
    A--;
    for(int v : adj[u]){
        if(par[v] == par[u] && !res[v]){
            dfsLow(v,c);
        }
    }
}
void dfsMid(int u,int c){
    if(B == 0) return;
    res[u] = c;
    B--;
    for(int v : adj[u]){
        if(!res[v]){
            dfsMid(v,c);
        }
    }
}

vector<int> find_split(int n,int a,int b,int c,vector<int> p,vector<int> q){
    N = n,M = p.size();
    for(int i=0;i<M;i++){
        adj[p[i]].push_back(q[i]);
        adj[q[i]].push_back(p[i]);
    }
    for(int i=0;i<N;i++){
        par[i] = i;
        sack[i].push_back(i);
    }
	color = {{a,1},{b,2},{c,3}};
	sort(color.begin(),color.end());
	A = color[0].first,B = color[1].first,C = color[2].first;
	res = vector<int>(N);
	dfsTree(0);
	for(int i=0;i<N;i++){
	    if(i != centroid){
	        for(int j : adjTree[i]){
	            if(j != centroid && par[i] != par[j]){
	                if(sack[par[i]].size() > sack[par[j]].size()){
	                    int idx = par[j];
	                    for(int it : sack[idx]){
	                        par[it] = par[i];
	                        sack[par[i]].push_back(it);
	                    }
	                    sack[idx].clear();
	                }else{
	                    int idx = par[i];
	                    for(int it : sack[idx]){
	                        par[it] = par[j];
	                        sack[par[j]].push_back(it);
	                    }
	                    sack[idx].clear();
	                }
	            }
	        }
            if(sack[par[i]].size() >= A){
                dfsLow(par[i],color[0].second);
                dfsMid(centroid,color[1].second);
                for(int &it : res) if(!it) it = color[2].second;
                return res;
            }
	    }
	}
	for(int i=0;i<N;i++){
	    if(i != centroid){
	        for(int j : adj[i]){
	            if(j != centroid && par[i] != par[j]){
	                if(sack[par[i]].size() > sack[par[j]].size()){
	                    int idx = par[j];
	                    for(int it : sack[idx]){
	                        par[it] = par[i];
	                        sack[par[i]].push_back(it);
	                    }
	                    sack[idx].clear();
	                }else{
	                    int idx = par[i];
	                    for(int it : sack[idx]){
	                        par[it] = par[j];
	                        sack[par[j]].push_back(it);
	                    }
	                    sack[idx].clear();
	                }
	            }
	        }
            if(sack[par[i]].size() >= A){
                dfsLow(par[i],color[0].second);
                dfsMid(centroid,color[1].second);
                for(int &it : res) if(!it) it = color[2].second;
                return res;
            }
	    }
	}
	return res;
}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:86:36: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   86 |             if(sack[par[i]].size() >= A){
      |                ~~~~~~~~~~~~~~~~~~~~^~~~
split.cpp:115:36: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  115 |             if(sack[par[i]].size() >= A){
      |                ~~~~~~~~~~~~~~~~~~~~^~~~

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