oj.uz

Submission #207405

# Submission time Handle Problem Language Result Execution time Memory
207405 2020-03-07T13:38:08 Z Segtree Collapse (JOI18_collapse) C++14
30 / 100
 8023 ms 19056 KB 
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<unordered_set>
#include"collapse.h"
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
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

#define Nmax 100010
#define B 300
typedef struct query{
	ll w,p,id;
}query;
bool comp_w(const query&a,const query&b){
	return a.w<b.w;
}
bool comp_p(const query&a,const query&b){
	return a.p<b.p;
}
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<T.size();i++){
		if(X[i]>Y[i])swap(X[i],Y[i]);
		//subtask2限定
		if(X[i]<=P[0]&&P[0]+1<=Y[i])X[i]=Y[i]=0;
	}
	for(int i=0;i<W.size();i++){
		qrys[W[i]].push_back((query){W[i],P[i],i});
	}
	vi fans(W.size());
	for(int L=0;L<T.size();L+=B){
		int R=min(L+B,(int)T.size());
		//{//base,s,basecmpを用意
			unordered_set<ll> base,s;
			for(int i=0;i<L;i++){
				ll has=(ll)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=(ll)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();}
		//}
		
		vector<query> Q;
		for(int i=L;i<R;i++){
			for(query tmp:qrys[i]){
				Q.push_back(tmp);
			}
		}
		sort(all(Q),comp_p);
		for(query qry:Q){
			unordered_set<ll> swork=s;
			for(int i=L;i<=qry.w;i++){
				ll has=(ll)X[i]*Nmax+Y[i];
				if(swork.count(has))swork.erase(has);
				else swork.insert(has);
			}
			unordered_set<ll> conc;
			for(auto e:swork){
				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();}
			fans[qry.id]=basecmp-conc.size()+scmp;
		}
	}
	return fans;
}

Compilation message

collapse.cpp: In function 'vi simulateCollapse(int, vi, vi, vi, vi, vi)':
collapse.cpp:47:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<T.size();i++){
              ~^~~~~~~~~
collapse.cpp:52:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<W.size();i++){
              ~^~~~~~~~~
collapse.cpp:56:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int L=0;L<T.size();L+=B){
              ~^~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 5368 KB Output is correct
2 Incorrect 12 ms 5624 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 14004 KB Output is correct
2 Correct 100 ms 12536 KB Output is correct
3 Correct 2243 ms 12536 KB Output is correct
4 Correct 360 ms 13996 KB Output is correct
5 Correct 2576 ms 12708 KB Output is correct
6 Correct 1546 ms 11704 KB Output is correct
7 Correct 3748 ms 16104 KB Output is correct
8 Correct 3625 ms 13092 KB Output is correct
9 Correct 87 ms 14812 KB Output is correct
10 Correct 209 ms 13740 KB Output is correct
11 Correct 2756 ms 13688 KB Output is correct
12 Correct 4126 ms 15532 KB Output is correct
13 Correct 5377 ms 17016 KB Output is correct
14 Correct 8023 ms 18988 KB Output is correct
15 Correct 6127 ms 19056 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 13924 KB Output is correct
2 Incorrect 137 ms 12568 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 5368 KB Output is correct
2 Incorrect 12 ms 5624 KB Output isn't correct
3 Halted 0 ms 0 KB -