oj.uz

Submission #338349

# Submission time Handle Problem Language Result Execution time Memory
338349 2020-12-23T03:39:08 Z GioChkhaidze Collapse (JOI18_collapse) C++14
0 / 100
 3774 ms 20924 KB 
#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=320;

bool f[N],fr[N];
int n,m,q,x,y,l,r,a,b,sz,sq,id,ids,cmp,idx,res;
int Tt[N],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=0; j<m; 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 j=0; j<Qu[i].size(); j++) {
			res=Qu[i][j];
			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

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:92:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |   for (int j=0; j<Qu[i].size(); j++) {
      |                 ~^~~~~~~~~~~~~
collapse.cpp:98:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |     for (int j=0; j<U[ids].size(); j++) {
      |                   ~^~~~~~~~~~~~~~
collapse.cpp:104:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |    for (int j=0; j<s.size(); j++)
      |                  ~^~~~~~~~~
collapse.cpp:110:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |    for (int j=0; j<s.size(); j++) {
      |                  ~^~~~~~~~~
collapse.cpp:118:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |    for (int j=0; j<s.size(); j++)
      |                  ~^~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3180 KB Output is correct
2 Correct 4 ms 2924 KB Output is correct
3 Correct 5 ms 2924 KB Output is correct
4 Correct 5 ms 2924 KB Output is correct
5 Correct 18 ms 3308 KB Output is correct
6 Correct 43 ms 3692 KB Output is correct
7 Incorrect 6 ms 3052 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 6372 KB Output is correct
2 Correct 45 ms 6380 KB Output is correct
3 Correct 513 ms 12524 KB Output is correct
4 Correct 56 ms 6892 KB Output is correct
5 Correct 1204 ms 13168 KB Output is correct
6 Correct 293 ms 7916 KB Output is correct
7 Correct 2159 ms 20588 KB Output is correct
8 Correct 1273 ms 16972 KB Output is correct
9 Incorrect 53 ms 7524 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 6372 KB Output is correct
2 Correct 58 ms 6488 KB Output is correct
3 Correct 61 ms 6892 KB Output is correct
4 Correct 71 ms 6892 KB Output is correct
5 Correct 141 ms 7312 KB Output is correct
6 Correct 332 ms 7916 KB Output is correct
7 Correct 2184 ms 17324 KB Output is correct
8 Correct 3774 ms 20924 KB Output is correct
9 Incorrect 86 ms 7524 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3180 KB Output is correct
2 Correct 4 ms 2924 KB Output is correct
3 Correct 5 ms 2924 KB Output is correct
4 Correct 5 ms 2924 KB Output is correct
5 Correct 18 ms 3308 KB Output is correct
6 Correct 43 ms 3692 KB Output is correct
7 Incorrect 6 ms 3052 KB Output isn't correct
8 Halted 0 ms 0 KB -