oj.uz

Submission #204338

# Submission time Handle Problem Language Result Execution time Memory
204338 2020-02-25T12:18:54 Z kshitij_sodani Split the Attractions (IOI19_split) C++17
11 / 100
 132 ms 13680 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 ind2=0;
int co=0;
int vis[200001];
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);
			
		}
	}
}
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){
		vis[0]=1;
		dfs(0);
		int st=1;
		vector<int> ans;
		for(int i=0;i<n;i++){
			ans.pb(0);
		}
		for(int j=0;j<b;j++){
			ans[stac[j]]=(int)2;

		}
		for(int i=0;i<n;i++){
			if(ans[i]==(int)2){
				continue;
			}
			ans[i]=st;
			st=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){
		vector<int> aa;
		return aa;
	}
	if(ind==-1){
		ind=0;
	}
	vis[ind]=1;
	dfs(ind);
	return anss;
}
/*int main(){

	return 0;
}*/

Compilation message

split.cpp: In function 'void dfs(int)':
split.cpp:20:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(stac.size()==bb){
     ~~~~~~~~~~~^~~~
split.cpp:23:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j=0;j<adj[no].size();j++){
              ~^~~~~~~~~~~~~~~
split.cpp:24:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(stac.size()==bb){
      ~~~~~~~~~~~^~~~
split.cpp: In function 'void dfs2(int)':
split.cpp:47:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j=0;j<adj[no].size();j++){
              ~^~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 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 Incorrect 8 ms 5752 KB jury found a solution, contestant did not
5 Halted 0 ms 0 KB -

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5752 KB ok, correct split
2 Correct 8 ms 5880 KB ok, correct split
3 Correct 10 ms 5752 KB ok, correct split
4 Correct 99 ms 12276 KB ok, correct split
5 Correct 81 ms 11380 KB ok, correct split
6 Correct 79 ms 11128 KB ok, correct split
7 Correct 91 ms 12916 KB ok, correct split
8 Correct 132 ms 13680 KB ok, correct split
9 Correct 86 ms 11376 KB ok, correct split
10 Correct 60 ms 12016 KB ok, correct split
11 Correct 61 ms 12016 KB ok, correct split
12 Correct 68 ms 12016 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 5756 KB WA in grader: Invalid length of the result.
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 9 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 Incorrect 8 ms 5752 KB jury found a solution, contestant did not
5 Halted 0 ms 0 KB -