Submission #151441

#	Time	Username	Problem	Language	Result	Execution time	Memory
151441		beso123	Split the Attractions (IOI19_split)	C++14	11 / 100	117 ms	13136 KiB

split

#include<bits/stdc++.h>
using namespace std;
int m,zx,z,x,d,e,used[100009],ka[10],la[100009];
vector <int> pas,g[100009];
void DFS(int v){
	if(ka[zx]==0)
        return;
	used[v]=1;
	pas[v]=zx;
	ka[zx]--;
	if(ka[zx]==0)
	return;
	for(vector <int>::iterator it=g[v].begin(); it!=g[v].end(); it++){
		if(used[(*it)]==1){
		DFS((*it));
		if(ka[zx]==0)
		return;
		}
	}
}
void DFS1(int v){
	if(ka[zx]==0)
        return;
	used[v]=1;
	pas[v]=zx;
	ka[zx]--;
	if(ka[zx]==0)
	return;
	for(vector <int>::iterator it=g[v].begin(); it!=g[v].end(); it++){
		if(used[(*it)]==1)
		continue;
		DFS1((*it));
		if(ka[zx]==0)
		return;
	}
}
vector <int> find_split(int n, int a, int b, int c, vector <int> p, vector <int> q){
	pas.resize(n);
	ka[1]=a;
	ka[2]=b;
	ka[3]=c;
	zx=0;
	m=p.size();
	for(int k=0;k<q.size();k++){
		g[p[k]].push_back(q[k]);
		g[q[k]].push_back(p[k]);
	}
	if(a!=1){
	zx=0;
	for(int k=0;k<n;k++){
		if(g[k].size()!=1)
            continue;
		if(used[k]==0){
			zx++;
			DFS(k);
		}
	}
	if(zx!=0){
	for(int k=0;k<n;k++)
        if(pas[k]==0)
        pas[k]=3;
	}
	else{
	    zx=0;
	    for(int k=0;k<n;k++){
	        if(used[k]==0){
	            zx++;
	            DFS(k);
	            break;
	        }
	    }
	    for(int k=0;k<n;k++){
	    	if(used[k]==1){
	    		for(vector <int>::iterator it=g[k].begin();it!=g[k].end(); it++){
					if(used[(*it)]==1)
                        continue;
					zx++;
					DFS((*it));
					break;
				}
				if(zx==2)
				break;
			}
		}
		for(int k=0;k<n;k++){
	        if(used[k]==0){
	            zx++;
	            DFS(k);
	            break;
	        }
	    }
	}
	}else{
		zx=2;
		DFS1(0);
		for(int k=0;k<n;k++){
			if(pas[k]==0){
            pas[k]=1;
			break;
			}
		}
		for(int k=0;k<n;k++)
            if(pas[k]==0)
            pas[k]=3;
	}
	return pas;

}
/*main(){
vector <int> v=find_split(9, 4, 2, 3, {0, 0, 0, 0, 0, 0, 1, 3, 4, 5},
{1, 2, 3, 4, 6, 8, 7, 7, 5, 6});
for(auto i : v)
    cout<<i<<' ';
    return 0;
}*/

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:44:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int k=0;k<q.size();k++){
              ~^~~~~~~~~

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