Submission #368859

#	Time	Username	Problem	Language	Result	Execution time	Memory
368859		kig9981	Collapse (JOI18_collapse)	C++17	100 / 100	8310 ms	393308 KiB

collapse

#include <bits/stdc++.h>
 
#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif
 
using namespace std;
 
const int BC=1000;
vector<int> adj[100000], BB;
vector<tuple<int,int,int>> qry;
vector<pair<int,int>> E, L[100000], R[100000];
map<pair<int,int>,int> idx;
int N, ans[100000], B[100000], LL[100000], color[100000], cnt[100000], RR[100000];
bool EX[100000];
 
void flip_edge(int c, int i)
{
	BB.push_back(c);
	EX[c]^=1;
}
 
int find_(int a)
{
	while(color[a]!=a) a=color[a];
	return a;
}
 
void union_(int a, int b)
{
	a=find_(a); b=find_(b);
	if(a==b) return;
	if(cnt[a]<cnt[b]) swap(a,b);
	cnt[color[b]=a]+=cnt[b];
	BB.push_back(b);
}
 
void restore(int sz)
{
	while(BB.size()>sz) {
		cnt[color[BB.back()]]-=cnt[BB.back()];
		color[BB.back()]=BB.back();
		BB.pop_back();
	}
}
 
void solve(int s, int e)
{
	int m=(s+e)>>1, bsz=BB.size(), bsz2;
	for(auto[v,r]: L[s]) if(r>=e) union_(E[v].first,E[v].second);
	for(auto[v,l]: R[e]) if(l<=s) union_(E[v].first,E[v].second);
	if(s==e) {
		ans[get<2>(qry[m])]=N-BB.size();
		restore(bsz);
		return;
	}
	bsz2=BB.size();
	for(int i=m;++i<e;) for(auto[v,l]: R[i]) if(l<=s) union_(E[v].first,E[v].second);
	solve(s,m);
	restore(bsz2);
	for(int i=m;i>s;i--) for(auto[v,r]: L[i]) if(r>=e) union_(E[v].first,E[v].second);
	solve(m+1,e);
	restore(bsz);
}
 
vector<int> simulateCollapse(int N, vector<int> T, vector<int> X, vector<int> Y, vector<int> W, vector<int> P)
{
	int C=T.size(), Q=W.size(), w, p;
	::N=N;
	for(int i=0;i<C;i++) {
		if(X[i]>Y[i]) swap(X[i],Y[i]);
		if(idx.count({X[i],Y[i]})==0) {
			idx[{X[i],Y[i]}]=E.size();
			E.emplace_back(X[i],Y[i]);
		}
		B[i]=idx[{X[i],Y[i]}];
		adj[X[i]].push_back(i);
		adj[Y[i]].push_back(i);
	}
	for(int i=0;i<Q;i++) qry.emplace_back(W[i],P[i],i);
	sort(qry.begin(),qry.end(),[&](tuple<int,int,int> a, tuple<int,int,int> b) {
		if(get<0>(a)/BC!=get<0>(b)/BC) return get<0>(a)/BC<get<0>(b)/BC;
		return get<1>(a)<get<1>(b);
	});
	memset(LL,w=p=-1,sizeof(LL));
	memset(RR,-1,sizeof(RR));
	for(int i=0;i<Q;i++) {
		auto[cw,cp,j]=qry[i];
		while(w<cw) {
			int c=B[++w];
			auto[a,b]=E[c];
			if(a<=p && p<b) continue;
			flip_edge(c,i);
		}
		while(w>cw) {
			int c=B[w--];
			auto[a,b]=E[c];
			if(a<=p && p<b) continue;
			flip_edge(c,i);
		}
		while(p<cp) {
			int c=++p;
			for(auto t: adj[c]) if(t<=w) flip_edge(B[t],i);
		}
		while(p>cp) {
			int c=p--;
			for(auto t: adj[c]) if(t<=w) flip_edge(B[t],i);
		}
		for(auto v: BB) if(RR[v]!=i) {
			RR[v]=i;
			if(LL[v]>-1 && !EX[v]) {
				L[LL[v]].emplace_back(v,i-1);
				R[i-1].emplace_back(v,LL[v]);
				LL[v]=-1;
			}
			else if(LL[v]==-1 && EX[v]) LL[v]=i;
		}
		BB.clear();
	}
	for(int i=0;i<E.size();i++) if(EX[i]) {
		L[LL[i]].emplace_back(i,Q-1);
		R[Q-1].emplace_back(i,LL[i]);
	}
	for(int i=0;i<N;i++) cnt[color[i]=i]=1;
	solve(0,Q-1);
	return vector<int>(ans,ans+Q);
}

Compilation message (stderr)

collapse.cpp: In function 'void restore(int)':
collapse.cpp:44:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   44 |  while(BB.size()>sz) {
      |        ~~~~~~~~~^~~
collapse.cpp: In function 'std::vector<int> simulateCollapse(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
collapse.cpp:124:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |  for(int i=0;i<E.size();i++) if(EX[i]) {
      |              ~^~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 30 / 30
• Subtask 3: 30 / 30
• Subtask 4: 35 / 35