#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){
~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
