oj.uz

Submission #204339

# Submission time Handle Problem Language Result Execution time Memory
204339 2020-02-25T12:19:52 Z kshitij_sodani Split the Attractions (IOI19_split) C++17
18 / 100
 121 ms 15732 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;
	dfs2(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
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5756 KB ok, correct split
2 Correct 9 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 5880 KB ok, correct split
6 Correct 8 ms 5752 KB ok, correct split
7 Correct 92 ms 15640 KB ok, correct split
8 Correct 92 ms 14836 KB ok, correct split
9 Correct 97 ms 15728 KB ok, correct split
10 Correct 74 ms 12280 KB ok, correct split
11 Correct 97 ms 15732 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 5756 KB ok, correct split
4 Correct 98 ms 12252 KB ok, correct split
5 Correct 78 ms 11508 KB ok, correct split
6 Correct 75 ms 11116 KB ok, correct split
7 Correct 82 ms 12916 KB ok, correct split
8 Correct 121 ms 13556 KB ok, correct split
9 Correct 79 ms 11380 KB ok, correct split
10 Correct 60 ms 12016 KB ok, correct split
11 Correct 63 ms 11888 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 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 8 ms 5756 KB ok, correct split
2 Correct 9 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 5880 KB ok, correct split
6 Correct 8 ms 5752 KB ok, correct split
7 Correct 92 ms 15640 KB ok, correct split
8 Correct 92 ms 14836 KB ok, correct split
9 Correct 97 ms 15728 KB ok, correct split
10 Correct 74 ms 12280 KB ok, correct split
11 Correct 97 ms 15732 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 5756 KB ok, correct split
15 Correct 98 ms 12252 KB ok, correct split
16 Correct 78 ms 11508 KB ok, correct split
17 Correct 75 ms 11116 KB ok, correct split
18 Correct 82 ms 12916 KB ok, correct split
19 Correct 121 ms 13556 KB ok, correct split
20 Correct 79 ms 11380 KB ok, correct split
21 Correct 60 ms 12016 KB ok, correct split
22 Correct 63 ms 11888 KB ok, correct split
23 Correct 63 ms 12016 KB ok, correct split
24 Incorrect 8 ms 5752 KB WA in grader: Invalid length of the result.
25 Halted 0 ms 0 KB -