oj.uz

Submission #1054551

# Submission time Handle Problem Language Result Execution time Memory
1054551 2024-08-12T10:36:36 Z aymanrs Collapse (JOI18_collapse) C++17
0 / 100
 24 ms 12652 KB 
#include "collapse.h"
#include <bits/stdc++.h>
using namespace std;
const int nx = 4e5+10;
list<pair<int,int>> st[nx];
int re[100000], sz[100000];
int a_,b_,x_,y_;
void adde(int i, int l, int r){
	if(r<a_||b_<l) return;
	if(a_<=l&&r<=b_){
		st[i].emplace_back(x_,y_);
		return;
	}
	int m = l+r>>1;
	adde(i<<1, l, m);adde(i<<1|1, m+1, r);
}
int ti[100000], co;
void dfs(int i, int l, int r){
	stack<pair<int, int>> s;
	for(auto [a,b] : st[i]){
		while(re[a]!=a) a=re[a];
		while(re[b]!=b) b=re[b];
		if(a==b)continue;
		co--;
		if(sz[a]>b){
			sz[a]+=sz[b];
			re[b]=a;
			s.emplace(a, b);
		} else {
			sz[b]+=sz[a];
			re[a]=b;
			s.emplace(b,a);
		}
	}
	st[i].clear();
	if(l!=r){
		int m = l+r>>1;
		dfs(i<<1, l, m);
		dfs(i<<1, m+1, r);
	} else {
		ti[l]=co;
	}
	while(!s.empty()){
		int a = s.top().first, b = s.top().second;
		s.pop();
		sz[a]-=sz[b];
		re[b]=b;
		co++;
	}
}
std::vector<int> simulateCollapse(
	int N,
	std::vector<int> T,
	std::vector<int> X,
	std::vector<int> Y,
	std::vector<int> W,
	std::vector<int> P
) {
	int q = W.size(), c = T.size();
	vector<int> ans(q);
	map<pair<int, int>, int> tadd;
	int p_ = P[0];
	for(int i = 0;i < N;i++){
		re[i]=i;
		sz[i]=1;
	}
	co=N;
	for(int i = 0;i < c;i++){
		if(min(X[i],Y[i]) <= p_ && max(X[i], Y[i]) > p_) continue;
		if(T[i]){
			auto p = tadd.find(make_pair(X[i], Y[i]));
			a_ = p->second;b_ = i-1;x_ = X[i];y_ = Y[i];
			adde(1, 0, c-1);
			p->second=-1;
		} else {
			tadd[make_pair(X[i], Y[i])] = i;
		}
	}
	for(auto p : tadd){
		if(p.second==-1) continue;
		a_ = p.second;b_ = c-1;x_ = p.first.first;y_ = p.first.second;
		adde(1,0,c-1);
	}
	dfs(1, 0, c-1);
	for(int i = 0;i < q;i++) ans[i] = ti[W[i]];
	return ans;
}

Compilation message

collapse.cpp: In function 'void adde(int, int, int)':
collapse.cpp:14:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   14 |  int m = l+r>>1;
      |          ~^~
collapse.cpp: In function 'void dfs(int, int, int)':
collapse.cpp:37:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |   int m = l+r>>1;
      |           ~^~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 12636 KB Output is correct
2 Incorrect 14 ms 12636 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 12652 KB Output is correct
2 Incorrect 13 ms 12636 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

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