Submission #368799

#	Time	Username	Problem	Language	Result	Execution time	Memory
368799		kig9981	Collapse (JOI18_collapse)	C++17	35 / 100	1977 ms	524292 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=300, SZ=1<<17;
vector<int> adj[100000], BB, tree[2*SZ];
vector<tuple<int,int,int>> qry;
vector<pair<int,int>> E;
map<pair<int,int>,int> idx;
int N, ans[100000], B[100000], LL[100000], color[100000], cnt[100000];
bool EX[100000];

void add_edge(int s, int e, int v)
{
	for(s+=SZ,e+=SZ;s<=e;s>>=1,e>>=1) {
		if(s&1) tree[s++].push_back(v);
		if(~e&1) tree[e--].push_back(v);
	}
}

void flip_edge(int c, int i)
{
	if(EX[c]) add_edge(LL[c],i-1,c);
	else LL[c]=i;
	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 bit, int s, int e)
{
	int m=(s+e)>>1, bsz=BB.size();
	if(qry.size()<=s) return;
	for(auto v: tree[bit]) union_(E[v].first,E[v].second);
	if(s==e) {
		ans[get<2>(qry[m])]=N-BB.size();
		restore(bsz);
		return;
	}
	solve(2*bit,s,m);
	solve(2*bit+1,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));
	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(int i=0;i<E.size();i++) if(EX[i]) add_edge(LL[i],Q-1,i);
	for(int i=0;i<N;i++) cnt[color[i]=i]=1;
	solve(1,0,SZ-1);
	return vector<int>(ans,ans+Q);
}

Compilation message (stderr)

collapse.cpp: In function 'void restore(int)':
collapse.cpp:53:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   53 |  while(BB.size()>sz) {
      |        ~~~~~~~~~^~~
collapse.cpp: In function 'void solve(int, int, int)':
collapse.cpp:63:15: warning: comparison of integer expressions of different signedness: 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   63 |  if(qry.size()<=s) return;
      |     ~~~~~~~~~~^~~
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:118: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]
  118 |  for(int i=0;i<E.size();i++) if(EX[i]) add_edge(LL[i],Q-1,i);
      |              ~^~~~~~~~~

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