oj.uz

Submission #577315

# Submission time Handle Problem Language Result Execution time Memory
577315 2022-06-14T13:52:40 Z jamielim Stranded Far From Home (BOI22_island) C++14
40 / 100
 1000 ms 47128 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];
set<int> comp;

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
	comp.erase(rb);
	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]=s[i];
		sets[i].pb(i);
	}
	for(int i=0;i<SZ(disc);i++){
		for(int j:ordered[i]){
			exist[j]=1;
			comp.insert(j);
		}
		for(int j:ordered[i]){
			for(int k:adj[j]){
				if(exist[k]){
					merge(j,k);
				}
			}
		}
		if(i+1<SZ(disc)){
			for(int j:comp){
				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:56:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |  scanf("%d%d",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~
island.cpp:59:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |   scanf("%lld",&s[i]);
      |   ~~~~~^~~~~~~~~~~~~~
island.cpp:70:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |   scanf("%d%d",&a,&b);
      |   ~~~~~^~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Correct 7 ms 14416 KB Output is correct
4 Correct 12 ms 14548 KB Output is correct
5 Correct 14 ms 14680 KB Output is correct
6 Correct 9 ms 14548 KB Output is correct
7 Correct 11 ms 14548 KB Output is correct
8 Correct 10 ms 14516 KB Output is correct
9 Correct 8 ms 14548 KB Output is correct
10 Correct 17 ms 14680 KB Output is correct
11 Correct 16 ms 14688 KB Output is correct
12 Correct 15 ms 14712 KB Output is correct
13 Correct 12 ms 14620 KB Output is correct
14 Correct 9 ms 14660 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14292 KB Output is correct
2 Correct 8 ms 14412 KB Output is correct
3 Correct 201 ms 40760 KB Output is correct
4 Correct 245 ms 42172 KB Output is correct
5 Execution timed out 1086 ms 38744 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14292 KB Output is correct
2 Execution timed out 1091 ms 39632 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14300 KB Output is correct
2 Correct 316 ms 38528 KB Output is correct
3 Correct 327 ms 38864 KB Output is correct
4 Correct 359 ms 40068 KB Output is correct
5 Correct 417 ms 45448 KB Output is correct
6 Correct 348 ms 43528 KB Output is correct
7 Correct 263 ms 44672 KB Output is correct
8 Correct 169 ms 38840 KB Output is correct
9 Correct 172 ms 26772 KB Output is correct
10 Correct 361 ms 47128 KB Output is correct
11 Correct 250 ms 39156 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Correct 7 ms 14416 KB Output is correct
4 Correct 12 ms 14548 KB Output is correct
5 Correct 14 ms 14680 KB Output is correct
6 Correct 9 ms 14548 KB Output is correct
7 Correct 11 ms 14548 KB Output is correct
8 Correct 10 ms 14516 KB Output is correct
9 Correct 8 ms 14548 KB Output is correct
10 Correct 17 ms 14680 KB Output is correct
11 Correct 16 ms 14688 KB Output is correct
12 Correct 15 ms 14712 KB Output is correct
13 Correct 12 ms 14620 KB Output is correct
14 Correct 9 ms 14660 KB Output is correct
15 Correct 8 ms 14292 KB Output is correct
16 Correct 8 ms 14412 KB Output is correct
17 Correct 201 ms 40760 KB Output is correct
18 Correct 245 ms 42172 KB Output is correct
19 Execution timed out 1086 ms 38744 KB Time limit exceeded
20 Halted 0 ms 0 KB -