Submission #401117

#	Time	Username	Problem	Language	Result	Execution time	Memory
401117		mosiashvililuka	Split the Attractions (IOI19_split)	C++17	100 / 100	187 ms	30420 KiB

split

#include "split.h"
#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,dp[100009],lf[100009],rg[100009],tim,up[100009],jm,pi,n,bo[100009],fx[100009],ans[100009],k[9],fla;
int A,B,C,D;
vector <int> v[100009],vsh[100009],vmsh[100009];
vector<int> res;
pair <int, int> p[100009],fe[10];
void dfsst(int q, int w){
	dp[q]=1;
	tim++;
	lf[q]=rg[q]=tim;
	up[q]=lf[q];
	for(vector <int>::iterator it=v[q].begin(); it!=v[q].end(); it++){
		if((*it)==w) continue;
		if(lf[(*it)]!=0){
			vmsh[q].push_back((*it));
			up[q]=min(up[q],lf[(*it)]);
			continue;
		}
		vsh[q].push_back((*it));
		dfsst((*it),q);
		dp[q]+=dp[(*it)];
		if(rg[q]<rg[(*it)]) rg[q]=rg[(*it)];
	}
}
void dfs3(int q, int w){
	if(e!=q){
		if(up[q]<lf[e]){
			pi++;
			p[pi].first=dp[q];
			p[pi].second=q;
			jm+=dp[q];
			return;
		}
	}
	for(vector <int>::iterator it=vsh[q].begin(); it!=vsh[q].end(); it++){
		dfs3((*it),q);
	}
}
void dfs4(int q, int w){
	if(bo[q]==1||C<=0) return;
	ans[q]=c;C--;
	for(vector <int>::iterator it=vsh[q].begin(); it!=vsh[q].end(); it++){
		dfs4((*it),q);
	}
}
void dfs5(int q, int w){
	if(D<=0) return;
	fx[q]=1;
	ans[q]=d;D--;
	for(vector <int>::iterator it=v[q].begin(); it!=v[q].end(); it++){
		if(ans[(*it)]!=0) continue;
		dfs5((*it),q);
	}
}
void print(){
	for(i=1; i<=a; i++){
		if(ans[i]==0) ans[i]=3;
	}
	for(i=1; i<=a; i++){
		res[i-1]=fe[ans[i]].second;
	}
}
void dfs(int q, int w){
	if(fla==1) return;
	if(dp[q]>=A){
		e=0;
		for(vector <int>::iterator it=vsh[q].begin(); it!=vsh[q].end(); it++){
			if(dp[(*it)]>=A){
				e=1; 
				break;
			}
		}
		if(e==0){
			jm=0;pi=0;e=q;
			dfs3(q,w);
			if(dp[q]-jm>n-A) return;
			c=dp[q];
			for(i=1; i<=pi+1; i++){
				if(c<=n-A) break;
				c-=p[i].first;
				bo[p[i].second]=1;
			}
			d=n-c;
			if(d>=B){
				C=A;D=B;
				c=1;d=2;
			}else{
				C=B;D=A;
				c=2;d=1;
			}
			dfs4(q,w);
			dfs5(1,0);
			print();
			fla=1;
			return;
		}
	}
	for(vector <int>::iterator it=vsh[q].begin(); it!=vsh[q].end(); it++){
		dfs((*it),q);
		if(fla==1) return;
	}
}
vector<int> find_split(int nn, int Aa, int Bb, int Cc, vector<int> pV, vector<int> qV) {
	a=nn;n=nn;
	A=Aa;B=Bb;C=Cc;
	fe[1]=make_pair(A,1);
	fe[2]=make_pair(B,2);
	fe[3]=make_pair(C,3);
	sort(fe+1,fe+4);
	A=fe[1].first;B=fe[2].first;C=fe[3].first;
	res.resize(a);
	for(i=0; i<res.size(); i++){
		res[i]=0;
	}
	for(i=0; i<pV.size(); i++){
		pV[i]++;qV[i]++;
		v[pV[i]].push_back(qV[i]);
		v[qV[i]].push_back(pV[i]);
	}
	dfsst(1,0);
	dfs(1,0);
	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:114:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |  for(i=0; i<res.size(); i++){
      |           ~^~~~~~~~~~~
split.cpp:117:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |  for(i=0; i<pV.size(); i++){
      |           ~^~~~~~~~~~

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