oj.uz

답안 #207395

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
207395 2020-03-07T13:16:39 Z Segtree Collapse (JOI18_collapse) C++14
30 / 100
 6635 ms 21524 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

//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<T.size();i++){
		if(X[i]>Y[i])swap(X[i],Y[i]);
		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){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=(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();}
		
		for(int i=L;i<R;i++){
			ll has=(ll)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 simulateCollapse(int, vi, vi, vi, vi, vi)':
collapse.cpp:38:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<T.size();i++){
              ~^~~~~~~~~
collapse.cpp:42:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<W.size();i++){
              ~^~~~~~~~~
collapse.cpp:46: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

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 5368 KB Output is correct
2 Incorrect 9 ms 5240 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 8812 KB Output is correct
2 Correct 38 ms 8988 KB Output is correct
3 Correct 1312 ms 12536 KB Output is correct
4 Correct 37 ms 9464 KB Output is correct
5 Correct 1598 ms 12668 KB Output is correct
6 Correct 66 ms 9976 KB Output is correct
7 Correct 2424 ms 16164 KB Output is correct
8 Correct 2253 ms 13136 KB Output is correct
9 Correct 41 ms 9448 KB Output is correct
10 Correct 41 ms 10488 KB Output is correct
11 Correct 72 ms 11768 KB Output is correct
12 Correct 2848 ms 17784 KB Output is correct
13 Correct 3791 ms 19616 KB Output is correct
14 Correct 6635 ms 21100 KB Output is correct
15 Correct 4770 ms 21524 KB Output is correct

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 8816 KB Output is correct
2 Incorrect 37 ms 8728 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 5368 KB Output is correct
2 Incorrect 9 ms 5240 KB Output isn't correct
3 Halted 0 ms 0 KB -