Submission #1054555

#	Time	Username	Problem	Language	Result	Execution time	Memory
1054555		aymanrs	Collapse (JOI18_collapse)	C++17	0 / 100	15 ms	12636 KiB

collapse

#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|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 (stderr)

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
• Subtask 2: 0 / 30
• Subtask 3: 0 / 30
• Subtask 4: 0 / 35