oj.uz

Submission #577296

# Submission time Handle Problem Language Result Execution time Memory
577296 2022-06-14T12:57:24 Z jamielim Stranded Far From Home (BOI22_island) C++14
0 / 100
 277 ms 66088 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;
int s[200005];
vector<int> ordered[200005];
vector<int> adj[200005];
bool imposs[200005];
bool exist[200005];
int par[200005];
int 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(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<int> disc;
	for(int i=1;i<=n;i++){
		scanf("%d",&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:53:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |  scanf("%d%d",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~
island.cpp:56:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |   scanf("%d",&s[i]);
      |   ~~~~~^~~~~~~~~~~~
island.cpp:67:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |   scanf("%d%d",&a,&b);
      |   ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14420 KB Output is correct
2 Correct 8 ms 14344 KB Output is correct
3 Correct 8 ms 14332 KB Output is correct
4 Runtime error 25 ms 29412 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Incorrect 168 ms 36828 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

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

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Runtime error 225 ms 66088 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14420 KB Output is correct
2 Correct 8 ms 14344 KB Output is correct
3 Correct 8 ms 14332 KB Output is correct
4 Runtime error 25 ms 29412 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -