oj.uz

Submission #204363

# Submission time Handle Problem Language Result Execution time Memory
204363 2020-02-25T14:04:10 Z kshitij_sodani Split the Attractions (IOI19_split) C++17
18 / 100
 134 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==bb){
			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 5752 KB ok, correct split
5 Correct 8 ms 5752 KB ok, correct split
6 Correct 8 ms 5752 KB ok, correct split
7 Correct 97 ms 14580 KB ok, correct split
8 Correct 103 ms 13684 KB ok, correct split
9 Correct 103 ms 14580 KB ok, correct split
10 Correct 80 ms 11128 KB ok, correct split
11 Correct 101 ms 14580 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 12276 KB ok, correct split
5 Correct 84 ms 11508 KB ok, correct split
6 Correct 81 ms 11128 KB ok, correct split
7 Correct 94 ms 12916 KB ok, correct split
8 Correct 134 ms 13684 KB ok, correct split
9 Correct 92 ms 11380 KB ok, correct split
10 Correct 63 ms 12144 KB ok, correct split
11 Correct 68 ms 12016 KB ok, correct split
12 Correct 70 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 5752 KB ok, correct split
5 Correct 8 ms 5752 KB ok, correct split
6 Correct 8 ms 5752 KB ok, correct split
7 Correct 97 ms 14580 KB ok, correct split
8 Correct 103 ms 13684 KB ok, correct split
9 Correct 103 ms 14580 KB ok, correct split
10 Correct 80 ms 11128 KB ok, correct split
11 Correct 101 ms 14580 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 12276 KB ok, correct split
16 Correct 84 ms 11508 KB ok, correct split
17 Correct 81 ms 11128 KB ok, correct split
18 Correct 94 ms 12916 KB ok, correct split
19 Correct 134 ms 13684 KB ok, correct split
20 Correct 92 ms 11380 KB ok, correct split
21 Correct 63 ms 12144 KB ok, correct split
22 Correct 68 ms 12016 KB ok, correct split
23 Correct 70 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 -