oj.uz

Submission #971796

# Submission time Handle Problem Language Result Execution time Memory
971796 2024-04-29T10:12:39 Z NintsiChkhaidze Stranded Far From Home (BOI22_island) C++17
0 / 100
 210 ms 32860 KB 
#include <bits/stdc++.h>
#define s second
#define f first
#define pb push_back
#define pii pair <int,int>
using namespace std;
 
const int N = 2e5 + 5;
int p[N],sz[N],ans[N];
pii b[N];
bool active[N];
vector <int> v[N],vec,cmp[N];
set <pii> st;



int P(int x){
	if(x==p[x]) return x;
	return p[x]=P(p[x]);
}

void dsu(int x,int y){
	int px=P(x),py=P(y);
	if (px==py) return;

	st.erase(st.find({sz[px],px}));
	st.erase(st.find({sz[py],py}));
	
	if (cmp[px].size() < cmp[py].size()) swap(px,py);
	sz[px] += sz[py];
	for (int k: cmp[py])
		cmp[px].pb(k);

	cmp[py].clear();
	sz[py]=0;
	st.insert({sz[px],px});
	p[py] = px;
}

void go(int x){
	active[x] = 1;
	st.insert({sz[x],x});
	for (int to: v[x]){
		if (active[to] && ans[to]) {
			dsu(x,to);
		}
	}
}

signed main(){
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
 
	int n,m;
	cin>>n>>m;	

	for (int i = 1; i <= n; i++){
		int a;
		cin>>a;
		sz[i] = a;
		p[i] = i;
		cmp[i].pb(i);
		b[i] = {a,i};
		vec.pb(a);
		ans[i]=1;
	}
	sort(vec.begin(),vec.end());
	vec.erase(unique(vec.begin(),vec.end()),vec.end());

	sort(b+1,b+n+1);

	for (int i=1;i<=m;i++){
		int a,bb;
		cin>>a>>bb;
		v[a].pb(bb);
		v[bb].pb(a);
	}

	int l = 1;
	for (int i=0;i<vec.size();i++){
		int val=vec[i];
		while (l <= n && b[l].f == val){
			go(b[l].s);
			++l;
		}

		if (i + 1 < vec.size()){
			int nxt = vec[i + 1];
			while (st.size() && (st.begin()->f) < nxt){
				int vert = st.begin()->s;
				for (int y: cmp[vert])
					ans[y]=0;
				st.erase(st.begin());
			}
		}
	}

	for (int i=1;i<=n;i++)
		cout<<ans[i];
}

Compilation message

island.cpp: In function 'int main()':
island.cpp:79:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |  for (int i=0;i<vec.size();i++){
      |               ~^~~~~~~~~~~
island.cpp:86:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |   if (i + 1 < vec.size()){
      |       ~~~~~~^~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12888 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 3 ms 12944 KB Output is correct
4 Incorrect 4 ms 12952 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12892 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Incorrect 118 ms 31704 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12892 KB Output is correct
2 Incorrect 170 ms 31688 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12888 KB Output is correct
2 Incorrect 210 ms 32860 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12888 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 3 ms 12944 KB Output is correct
4 Incorrect 4 ms 12952 KB Output isn't correct
5 Halted 0 ms 0 KB -