Submission #507136

#	Time	Username	Problem	Language	Result	Execution time	Memory
507136		jamezzz	Comparing Plants (IOI20_plants)	C++17	0 / 100	29 ms	13928 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>
using namespace std;

#define pf printf
#define pb push_back
#define maxn 200005

int n;

inline int nx(int i){
	return (i+1)%n;
}

inline int pv(int i){
	return (i+n-1)%n;
}

int done[maxn],val[maxn],vis[maxn],num[maxn];
vector<int> AL[maxn],post;

void dfs(int u){
	vis[u]=true;
	for(int v:AL[u]){
		if(!vis[v])dfs(v);
	}
	post.pb(u);
}

void dfs2(int u){
	vis[u]=true;
	for(int v:AL[u]){
		if(!vis[v]){
			num[v]=num[u];
			dfs2(v);
		}
	}
}

void init(int k,vector<int> r){
	n=(int)r.size();
	queue<int> process;
	
	for(int i=0;i<n;++i){
		if(r[i]==0){
			process.push(i);
		}
	}
	
	while(!process.empty()){
		int x=process.front();
		process.pop();
		int t=x;
		for(int i=0;i<k-1;++i){
			t=nx(t);
			if(r[t]!=0)AL[t].pb(x);
		}
		t=x;
		for(int i=0;i<k-1;++i){
			t=pv(t);
			if(r[t]!=0){
				AL[t].pb(x);
				--r[t];
				if(r[t]==0)process.push(t);
			}
			else AL[x].pb(t);
		}
	}
	
	/*
	for(int i=0;i<n;++i){
		pf("%d: ",i);
		for(int j:AL[i])pf("%d ",j);
		pf("\n");
	}
	*/
	
	for(int i=0;i<n;++i){
		if(vis[i]==0)dfs(i);
	}
	
	assert(post.size()==n);
	for(int i=n-1;i>=0;--i){
		val[post[i]]=n-i;
	}
	
	int cnt=0;
	memset(vis,0,sizeof vis);
	for(int i=n-1;i>=0;--i){
		if(!vis[post[i]]){
			num[post[i]]=cnt++;
			dfs2(post[i]);
		}
	}
	
	/*
	for(int i=0;i<n;++i)pf("%d ",val[i]);
	pf("\n");
	*/
	return;
}

int compare_plants(int x,int y){
	if(num[x]!=num[y])return 0;
	if(val[x]>val[y])return 1;
	if(val[x]<val[y])return -1;
	return 0;
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from plants.cpp:2:
plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:82:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   82 |  assert(post.size()==n);
      |         ~~~~~~~~~~~^~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25