Submission #338362

#	Time	Username	Problem	Language	Result	Execution time	Memory
338362		GioChkhaidze	Collapse (JOI18_collapse)	C++14	100 / 100	5898 ms	23164 KiB

collapse

#pragma GCC diagnostic warning "-std=c++11"
#include <bits/stdc++.h>
#include "collapse.h"

#define pb push_back
#define F first
#define S second

using namespace std;

const int N=1e5+5;
const int Sq=777;

bool f[N],fr[N],Tt[N];
int n,m,q,x,y,l,r,a,b,sz,sq,id,ids,cmp,idx,res;
int Xx[N],Yy[N],Pp[N],Ww[N],p[N],last[N],curl[N],ed[N];
  
vector < int > s,ans,Qu[Sq],U[N];
vector < pair < pair < int , int > , int > > rec;

map < pair < int , int > , int > fid;

void roll() {
	while (rec.size()) {
		x=rec.back().F.S;
		p[x]=rec.back().F.F;
		cmp=rec.back().S;
		rec.pop_back();
	}
}

int P(int x,bool tp) {
	if (p[x]==x) return x;
	y=P(p[x],tp);
	if (tp) rec.pb({{p[x],x},cmp});
	return p[x]=y;
}

void Uni(int a,int b,bool tp) {
	a=P(a,tp),b=P(b,tp);
	if (a==b) return ;
	if (tp) rec.pb({{p[b],b},cmp});
	p[b]=a;
	--cmp;
}

bool comp(int a,int b) {
	return (Pp[a]<Pp[b]);
}

void Solve() {
	sz=0;
	fid.clear();
	for (int i=0; i<m; i++) {
		if (Xx[i]>Yy[i]) swap(Xx[i],Yy[i]);	
		if (!fid[{Xx[i],Yy[i]}]) fid[{Xx[i],Yy[i]}]=++sz;
		ed[i]=fid[{Xx[i],Yy[i]}];
	}
	
	for (int i=0; i<q; i++) 
		Qu[Ww[i]/sq].pb(i);

	for (int i=0; i*sq<m; i++) {
		if (!Qu[i].size()) continue;
		sort(Qu[i].begin(),Qu[i].end(),comp);		
		l=i*sq,r=min((i+1)*sq,m);
		
		for (int j=0; j<n; j++) 
			p[j]=j,U[j].clear();
	
		for (int j=1; j<=sz; j++) 
			f[j]=fr[j]=false,last[j]=-1;

		s.clear();
		for (int j=l; j<r; j++) 
			if (!f[ed[j]]) f[ed[j]]=true,s.pb(ed[j]);	

		for (int j=l-1; j>=0; j--) { 
			idx=ed[j]; 
			if (fr[idx]) continue;
			fr[idx]=true;
			last[idx]=j;
			if (f[idx]) continue; 
			if (!Tt[j]) U[Yy[j]].pb(Xx[j]); 
		}
		
		cmp=0;
		ids=-1;
		for (int k=0; k<Qu[i].size(); k++) {
			res=Qu[i][k];
			x=Pp[res]; 
			
			while (ids+1<=x) {
				++ids,++cmp;
				for (int j=0; j<U[ids].size(); j++) {
					a=U[ids][j],b=ids;
					Uni(a,b,0);
				}				
			}
			
			for (int j=0; j<s.size(); j++) 
				curl[s[j]]=last[s[j]];

			for (int j=l; j<=Ww[res]; j++) 
				curl[ed[j]]=j;
			
			for (int j=0; j<s.size(); j++) {
				id=curl[s[j]];
				if (id!=-1 && !Tt[id] && Yy[id]<=x) 
					Uni(Xx[id],Yy[id],1);
			}

			ans[res]+=cmp;
			for (int j=0; j<s.size(); j++) 
				curl[s[j]]=-1;
				
			roll();
		}
		
		Qu[i].clear();
	}
}

vector<int> simulateCollapse(
	int N,
	vector<int> T,
	vector<int> X,
	vector<int> Y,
	vector<int> W,
	vector<int> P
) {
	n=N,m=T.size(),sq=sqrt(m),q=W.size();
	for (int i=0; i<m; i++) 
		Tt[i]=T[i],Xx[i]=X[i],Yy[i]=Y[i];
	
	ans.resize(q,0);	
	for (int i=0; i<q; i++) 
		Ww[i]=W[i],Pp[i]=P[i];
	
	Solve();
	
	for (int i=0; i<m; i++) 
		Xx[i]=n-1-Xx[i],Yy[i]=n-1-Yy[i];
	
	for (int i=0; i<q; i++) 
		Pp[i]=n-1-(Pp[i]+1);

	Solve();
	return ans;
}

Compilation message (stderr)

collapse.cpp:1:32: warning: '-std=c++11' is not an option that controls warnings [-Wpragmas]
    1 | #pragma GCC diagnostic warning "-std=c++11"
      |                                ^~~~~~~~~~~~
collapse.cpp: In function 'void Solve()':
collapse.cpp:89:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |   for (int k=0; k<Qu[i].size(); k++) {
      |                 ~^~~~~~~~~~~~~
collapse.cpp:95:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |     for (int j=0; j<U[ids].size(); j++) {
      |                   ~^~~~~~~~~~~~~~
collapse.cpp:101:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |    for (int j=0; j<s.size(); j++)
      |                  ~^~~~~~~~~
collapse.cpp:107:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |    for (int j=0; j<s.size(); j++) {
      |                  ~^~~~~~~~~
collapse.cpp:114:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |    for (int j=0; j<s.size(); j++)
      |                  ~^~~~~~~~~

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