oj.uz

Submission #577311

# Submission time Handle Problem Language Result Execution time Memory
577311 2022-06-14T13:46:53 Z jamielim Stranded Far From Home (BOI22_island) C++14
0 / 100
 294 ms 39040 KB 
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ii,ii> i4;
const int MOD=1000000007;
const int INF=1012345678;
const ll LLINF=1012345678012345678LL;
const double PI=3.1415926536;
const double EPS=1e-14;

int n,m;
ll s[200005];
vector<int> ordered[200005];
vector<int> adj[200005];
bool imposs[200005];
bool exist[200005];
int par[200005];
ll sz[200005];
vector<int> sets[200005];

int root(int x){
	return par[x]=(par[x]==x?x:root(par[x]));
}

void merge(int x,int y){
	int ra=root(x),rb=root(y);
	if(ra==rb)return;
	if(SZ(sets[ra])<SZ(sets[rb])){
		swap(ra,rb);
		swap(x,y);
	}
	// rb is smaller
	for(int i:sets[rb])sets[ra].pb(i);
	sz[ra]+=sz[rb];
	par[rb]=ra;
}

void mark_imposs(int x){
	for(int i:sets[x]){
		imposs[i]=1;
	}
	sets[x].clear();
}

int main(){
	scanf("%d%d",&n,&m);
	vector<ll> disc;
	for(int i=1;i<=n;i++){
		scanf("%lld",&s[i]);
		disc.pb(s[i]);
	}
	sort(ALL(disc));
	disc.resize(unique(ALL(disc))-disc.begin());
	for(int i=1;i<=n;i++){
		int x=lower_bound(ALL(disc),s[i])-disc.begin();
		ordered[x].pb(i);
	}
	int a,b;
	for(int i=0;i<m;i++){
		scanf("%d%d",&a,&b);
		adj[a].pb(b);
		adj[b].pb(a);
	}
	for(int i=1;i<=n;i++){
		par[i]=i;
		sz[i]=1;
		sets[i].pb(i);
	}
	for(int i=0;i<SZ(disc);i++){
		for(int j:ordered[i]){
			exist[j]=1;
		}
		for(int j:ordered[i]){
			for(int k:adj[j]){
				if(exist[k]){
					merge(j,k);
				}
			}
		}
		if(i+1<SZ(disc)){
			for(int j:ordered[i]){
				int p=root(j);
				if(sz[p]<disc[i+1]&&!imposs[p]){
					mark_imposs(p);
				}
			}
		}
	}
	for(int i=1;i<=n;i++){
		if(imposs[i])printf("0");
		else printf("1");
	}
}

Compilation message

island.cpp: In function 'int main()':
island.cpp:54:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |  scanf("%d%d",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~
island.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |   scanf("%lld",&s[i]);
      |   ~~~~~^~~~~~~~~~~~~~
island.cpp:68:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |   scanf("%d%d",&a,&b);
      |   ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 14420 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 14316 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14408 KB Output is correct
2 Incorrect 288 ms 39040 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Incorrect 294 ms 34320 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 14420 KB Output isn't correct
2 Halted 0 ms 0 KB -