oj.uz

Submission #204362

# Submission time Handle Problem Language Result Execution time Memory
204362 2020-02-25T14:03:11 Z kshitij_sodani Split the Attractions (IOI19_split) C++17
18 / 100
 122 ms 14580 KB 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#include <split.h>
#define mp make_pair
#define pb push_back
/*#define a first
#define b second*/
vector<int> adj[200001];
vector<int> stac;
int bb;
int aa;
int cc;
int ind7;
int ind2=0;
int co=0;
int vis[200001];
int dd;
vector<int> anss;
void dfs(int no){
	stac.pb(no);
	if(stac.size()==bb){
		return ;
	}
	for(int j=0;j<adj[no].size();j++){
		if(stac.size()==bb){
				return;
			}
		int nn=adj[no][j];
		if(vis[nn]==0){
			vis[nn]=1;
			dfs(nn);
			
		}
	}
}
void dfs2(int no){
	co+=1;
	if(co<=aa){
		anss[no]=1;
	}
	else if(co<=aa+bb){
		anss[no]=2;

	}
	else{
		anss[no]=3;
	}
	for(int j=0;j<adj[no].size();j++){

		int nn=adj[no][j];
		if(vis[nn]==0){
			vis[nn]=1;
			dfs2(nn);
			
		}
	}
}
int size2[200001];
vector<pair<int,int>> pos;

void dfs3(int no,int par=-1){
	size2[no]=1;
	int st=1;
	for(int j=0;j<adj[no].size();j++){
		int nn=adj[no][j];
		if(nn==par){
			continue;
		}
		dfs3(nn,no);
		size2[no]+=size2[nn];
		if(size2[nn]>=aa){
			st=0;
		}
	}
	if(st==1 and size2[no]>=aa){
		pos.pb(mp(no,par));
	}
}
int val[3];
void dfs4(int no,int par){
	co+=1;
	anss[no]=val[0];
	if(co==aa){
		return;
	}
	for(int j=0;j<adj[no].size();j++){
		if(co==aa){
			return;
		}
		int nn=adj[no][j];
		if(nn==par){
			continue;
		}
		if(ind7==nn){
			continue;
		}
		dfs4(nn,no);
	}
}
void dfs5(int no,int par){
	co+=1;
	anss[no]=val[1];
	if(co==bb){
		return;
	}
	for(int j=0;j<adj[no].size();j++){
		if(co==aa){
			return;
		}
		int nn=adj[no][j];
		if(nn==par){
			continue;
		}
		if(ind7==nn){
			continue;
		}
		dfs5(nn,no);
	}
}
vector<int> find_split(int n,int a,int b,int c,vector<int> p,vector<int> q){
	int m=p.size();

	bb=b;
	aa=a;
	cc=c;
	memset(vis,0,sizeof(vis));
	for(int i=0;i<m;i++){
		adj[p[i]].pb(q[i]);
		adj[q[i]].pb(p[i]);
	}
	if(a==1){
		//st2
		vis[0]=1;
		dfs(0);
		int st2=1;
		vector<int> ans;
		for(int i=0;i<n;i++){
			ans.pb(0);
		}
		for(int j=0;j<b;j++){
			ans[stac[j]]=2;

		}
		for(int i=0;i<n;i++){
			if(ans[i]==2){
				continue;
			}
			ans[i]=st2;
			st2=3;
		}
		return ans;
	}
	int st=0;
	int ind=-1;
	for(int i=0;i<n;i++){
		anss.pb(0);
	}
	for(int i=0;i<n;i++){
		if(adj[i].size()>2){
			st=1;
		}
		else if(adj[i].size()==1){
			ind=i;
		}

	}
	if(st==1){
		if(m==n-1){
			vector<int> ss;
			ss.pb(a);
			ss.pb(b);
			ss.pb(c);
			sort(ss.begin(),ss.end());
			for(int i=0;i<3;i++){
				if(ss[i]==a){
					val[i]=1;
				}
				else if(ss[i]==b){
					val[i]=2;
				}
				else{
					val[i]=3;
				}
			}
			a=ss[0];
			b=ss[1];
			c=ss[2];
			aa=a;
			bb=b;
			cc=c;
			dfs3(0,-1);
			ind7=-1;
			int par5=-1;
		/*	for(int i=0;i<n;i++){
				cout<<size[i]<<" ";
			}
			cout<<endl;*/
			for(int j=0;j<pos.size();j++){
				if(n-size2[pos[j].first]>=a){
					ind7=pos[j].first;
					par5=pos[j].second;
					break;
				}
			}
			if(ind7==-1){
				return anss;
			}
			if(size2[ind7]<b){
				int ind8=ind7;
				ind7=-1;
				co=0;
				dfs4(ind8,par5);
				ind7=ind8;
				co=0;
				dfs5(0,-1);
				for(int i=0;i<n;i++){
					if(anss[i]==0){
						anss[i]=val[2];
					}
				}
			}
			else{
				int ind8=ind7;
				ind7=-1;
				co=0;
				dfs5(ind8,par5);
				co=0;
				ind7=ind8;
				dfs4(0,-1);
				for(int i=0;i<n;i++){
					if(anss[i]==0){
						anss[i]=val[2];
					}
				}
			}
			return anss;
		}
		vector<int> rip;
		return rip;
	}
	else{
		//st1
		if(ind==-1){
			ind=0;
		}
		vis[ind]=1;
		dfs2(ind);
	}
	return anss;
}
/*int main(){
	vector<int> ans10;
	
	ans10=find_split(6, 2, 3, 1, {0, 1, 2, 3, 4}, {1, 2, 3, 4, 5});
	for(int i=0;i<ans10.size();i++){
		cout<<ans10[i]<<endl;
	}

	return 0;
}*/

Compilation message

split.cpp: In function 'void dfs(int)':
split.cpp:22:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(stac.size()==bb){
     ~~~~~~~~~~~^~~~
split.cpp:25:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j=0;j<adj[no].size();j++){
              ~^~~~~~~~~~~~~~~
split.cpp:26:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(stac.size()==bb){
      ~~~~~~~~~~~^~~~
split.cpp: In function 'void dfs2(int)':
split.cpp:49:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j=0;j<adj[no].size();j++){
              ~^~~~~~~~~~~~~~~
split.cpp: In function 'void dfs3(int, int)':
split.cpp:65:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j=0;j<adj[no].size();j++){
              ~^~~~~~~~~~~~~~~
split.cpp: In function 'void dfs4(int, int)':
split.cpp:87:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j=0;j<adj[no].size();j++){
              ~^~~~~~~~~~~~~~~
split.cpp: In function 'void dfs5(int, int)':
split.cpp:107:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j=0;j<adj[no].size();j++){
              ~^~~~~~~~~~~~~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:199:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0;j<pos.size();j++){
                ~^~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5752 KB ok, correct split
2 Correct 8 ms 5752 KB ok, correct split
3 Correct 8 ms 5752 KB ok, correct split
4 Correct 8 ms 5880 KB ok, correct split
5 Correct 8 ms 5752 KB ok, correct split
6 Correct 8 ms 5752 KB ok, correct split
7 Correct 93 ms 14564 KB ok, correct split
8 Correct 89 ms 13684 KB ok, correct split
9 Correct 103 ms 14580 KB ok, correct split
10 Correct 73 ms 11128 KB ok, correct split
11 Correct 91 ms 14576 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5752 KB ok, correct split
2 Correct 8 ms 5752 KB ok, correct split
3 Correct 8 ms 5752 KB ok, correct split
4 Correct 99 ms 12292 KB ok, correct split
5 Correct 83 ms 11636 KB ok, correct split
6 Correct 75 ms 11128 KB ok, correct split
7 Correct 87 ms 12916 KB ok, correct split
8 Correct 122 ms 13608 KB ok, correct split
9 Correct 76 ms 11380 KB ok, correct split
10 Correct 61 ms 12016 KB ok, correct split
11 Correct 61 ms 12012 KB ok, correct split
12 Correct 63 ms 12016 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 5752 KB invalid split: #1=4, #2=1, #3=0
2 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 5752 KB WA in grader: Invalid length of the result.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5752 KB ok, correct split
2 Correct 8 ms 5752 KB ok, correct split
3 Correct 8 ms 5752 KB ok, correct split
4 Correct 8 ms 5880 KB ok, correct split
5 Correct 8 ms 5752 KB ok, correct split
6 Correct 8 ms 5752 KB ok, correct split
7 Correct 93 ms 14564 KB ok, correct split
8 Correct 89 ms 13684 KB ok, correct split
9 Correct 103 ms 14580 KB ok, correct split
10 Correct 73 ms 11128 KB ok, correct split
11 Correct 91 ms 14576 KB ok, correct split
12 Correct 8 ms 5752 KB ok, correct split
13 Correct 8 ms 5752 KB ok, correct split
14 Correct 8 ms 5752 KB ok, correct split
15 Correct 99 ms 12292 KB ok, correct split
16 Correct 83 ms 11636 KB ok, correct split
17 Correct 75 ms 11128 KB ok, correct split
18 Correct 87 ms 12916 KB ok, correct split
19 Correct 122 ms 13608 KB ok, correct split
20 Correct 76 ms 11380 KB ok, correct split
21 Correct 61 ms 12016 KB ok, correct split
22 Correct 61 ms 12012 KB ok, correct split
23 Correct 63 ms 12016 KB ok, correct split
24 Incorrect 8 ms 5752 KB invalid split: #1=4, #2=1, #3=0
25 Halted 0 ms 0 KB -