Submission #207387

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
207387	2020-03-07T13:08:11 Z	Segtree	Collapse (JOI18_collapse)	C++14	Compilation error	0 ms	0 KB

collapse

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include"collapse.h"
using namespace std;
typedef long long ll;
typedef vector<int> vi;
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
#define all(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define mod 1000000007
#define mad(a,b) a=(a+b)%mod
namespace solver2{
#define Nmax 100010
#define B 300
typedef struct query{
	ll p,id;
}query;
vector<query> qrys[Nmax];

bool vis[Nmax];
vector<ll> graph[Nmax];
ll cmp[Nmax];
void dfs(ll x,ll cmps){
	if(vis[x])return;
	vis[x]=1;
	if(cmps>=0)cmp[x]=cmps;
	for(auto y:graph[x])dfs(y,cmps);
}

vi simulateCollapse(int N,vi T,vi X,vi Y,vi W,vi P){
	for(int i=0;i<Nmax;i++){
		qrys[i].clear();
		graph[i].clear();
	}
	
	for(int i=0;i<N;i++){
		if(X[i]>Y[i])swap(X[i],Y[i]);
		if(X[i]<=P[i]&&P[i]+1<=Y[i])X[i]=Y[i]=0;
	}
	for(int i=0;i<W.size();i++){
		qrys[W[i]].push_back((query){P[i],i});
	}
	vi fans(W.size());
	for(int L=0;L<T.size();L+=B){
		int R=min(L+B,(int)T.size());
		unordered_set<ll> base,s;
		for(int i=0;i<L;i++){
			ll has=X[i]*Nmax+Y[i];
			if(base.count(has))base.erase(has);
			else base.insert(has);
		}
		for(int i=L;i<R;i++){
			ll has=X[i]*Nmax+Y[i];
			if(base.count(has)){
				base.erase(has);
				s.insert(has);
			}
		}
		for(int i=0;i<N;i++){vis[i]=0;graph[i].clear();}
		for(auto e:base){
			ll x=e/Nmax,y=e%Nmax;
			graph[x].push_back(y);
			graph[y].push_back(x);
		}
		ll basecmp=0;
		for(int i=0;i<N;i++)if(vis[i]==0){
			dfs(i,basecmp++);
		}
		for(int i=0;i<N;i++){vis[i]=0;graph[i].clear();}
		
		for(int i=L;i<R;i++){
			ll has=X[i]*Nmax+Y[i];
			if(s.count(has))s.erase(has);
			else s.insert(has);
			unordered_set<ll> conc;
			for(auto e:s){
				ll x=e/Nmax,y=e%Nmax;
				x=cmp[x],y=cmp[y];
				graph[x].push_back(y);
				graph[y].push_back(x);
				conc.insert(x);
				conc.insert(y);
			}
			ll scmp=0;
			for(auto i:conc)if(vis[i]==0){
				dfs(i,-1);
				scmp++;
			}
			for(auto i:conc){vis[i]=0;graph[i].clear();}
			for(query qry:qrys[i]){
				fans[qry.id]=basecmp-conc.size()+scmp;
			}
		}
	}
	return fans;
}
}

Compilation message

collapse.cpp: In function 'vi solver2::simulateCollapse(int, vi, vi, vi, vi, vi)':
collapse.cpp:43:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<W.size();i++){
              ~^~~~~~~~~
collapse.cpp:47:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int L=0;L<T.size();L+=B){
              ~^~~~~~~~~
collapse.cpp:49:3: error: 'unordered_set' was not declared in this scope
   unordered_set<ll> base,s;
   ^~~~~~~~~~~~~
collapse.cpp:49:19: error: expected primary-expression before '>' token
   unordered_set<ll> base,s;
                   ^
collapse.cpp:49:21: error: 'base' was not declared in this scope
   unordered_set<ll> base,s;
                     ^~~~
collapse.cpp:49:26: error: 's' was not declared in this scope
   unordered_set<ll> base,s;
                          ^
collapse.cpp:63:14: error: unable to deduce 'auto&&' from 'base'
   for(auto e:base){
              ^~~~
collapse.cpp:65:23: error: 'y' was not declared in this scope
    graph[x].push_back(y);
                       ^
collapse.cpp:78:20: error: expected primary-expression before '>' token
    unordered_set<ll> conc;
                    ^
collapse.cpp:78:22: error: 'conc' was not declared in this scope
    unordered_set<ll> conc;
                      ^~~~
collapse.cpp:78:22: note: suggested alternative: 'clone'
    unordered_set<ll> conc;
                      ^~~~
                      clone
collapse.cpp:79:15: error: unable to deduce 'auto&&' from 's'
    for(auto e:s){
               ^
collapse.cpp:81:14: error: 'y' was not declared in this scope
     x=cmp[x],y=cmp[y];
              ^
collapse.cpp:88:15: error: unable to deduce 'auto&&' from 'conc'
    for(auto i:conc)if(vis[i]==0){
               ^~~~
collapse.cpp:92:15: error: unable to deduce 'auto&&' from 'conc'
    for(auto i:conc){vis[i]=0;graph[i].clear();}
               ^~~~