#ifndef LOCAL
#include "collapse.h"
#endif // LOCAL
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 1e5 + 5;
typedef pair<int,int> ii;
int n , m , q;
vector<int> Q[maxn];
int type[maxn] , x[maxn] , y[maxn];
int p[maxn] , w[maxn];
int in[maxn] , out[maxn];
int res[maxn];
struct Dsurollback{
vector<pair<int*,int>> data;
int lab[maxn];
int FindLab(int u){
return lab[u] < 0 ? u : FindLab(lab[u]);
}
void Change(int & u , int v){
data.pb(mp(&u,u));
u = v;
}
void rollback(int sz){
while(data.size() > sz){
(*data.back().first) = data.back().second;
data.pop_back();
}
}
int cnt = 0;
void Merge(int u , int v){
u = FindLab(u);v = FindLab(v);
if(u == v)return;
if(lab[u] > lab[v])swap(u,v);
Change(lab[u],lab[u]+lab[v]);
Change(lab[v],u);
Change(cnt,cnt+1);
}
int cur(){return data.size();};
void reset(){
fill_n(lab,maxn,-1);cnt = 0;
data.clear();
}
}Dsu;
void solve(){
const int MAGIC = 400;
vector<int> sp , norm;
for(int l = 0 ; l < m ; l += MAGIC){
int r = min(m,l+MAGIC) - 1;
vector<int> q;
for(int i = 0 ; i <= r ; ++i){
if(i >= l)for(auto & id : Q[i])q.pb(id);
if(out[i] < l || type[i] == 1)continue;
if(i >= l || out[i] <= r)sp.pb(i);//in[i] >= l || (in[i] < l && out[i] >= l && out[i] <= r)
else norm.pb(i);
}
sort(norm.begin(),norm.end(),[&](const int a , const int b){return y[a] < y[b];});
sort(q.begin(),q.end(),[&](const int a , const int b){return p[a] < p[b];});
int qi = 0 , qe = 0;
Dsu.reset();
for(int i = 0 ; i < n ; ++i){
while(qe < norm.size() && y[norm[qe]] == i)Dsu.Merge(x[norm[qe]] , y[norm[qe]]),++qe;
while(qi < q.size() && p[q[qi]] == i){
int id = q[qi];
int pre = Dsu.cur();
for(auto & c : sp){
if(y[c] <= i && c <= w[id] && w[id] < out[c])Dsu.Merge(x[c],y[c]);
}
res[id] -= Dsu.cnt;
Dsu.rollback(pre);
++qi;
}
}
sort(norm.begin(),norm.end(),[&](const int a , const int b){return x[a] > x[b];});
sort(q.begin(),q.end(),[&](const int a , const int b){return p[a] > p[b];});
qi = 0 , qe = 0;
Dsu.reset();
for(int i = n - 1 ; i >= 0 ; --i){
while(qe < norm.size() && x[norm[qe]] == i)Dsu.Merge(x[norm[qe]] , y[norm[qe]]),++qe;
while(qi < q.size() && p[q[qi]] == i - 1){
int id = q[qi];
int pre = Dsu.cur();
for(auto & c : sp){
if(x[c] > i && c <= w[id] && w[id] < out[c])Dsu.Merge(x[c],y[c]);
}
res[id] -= Dsu.cnt;
Dsu.rollback(pre);
++qi;
}
}
Dsu.reset();
}
}
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();q = W.size();
for(int i = 0 ; i < m ; ++i){
type[i] = 1;
x[i] = X[i];y[i] = Y[i];
if(x[i] > y[i])swap(x[i],y[i]);
}
for(int i = 0 ; i < q ; ++i){
p[i] = P[i];w[i] = W[i];
Q[w[i]].pb(i);
}
map<ii,int> mmap;
for(int i = 0 ; i < m ; ++i){
if(type[i] == 0){
mmap[mp(x[i],y[i])] = i;
}else{
out[mmap[mp(x[i],y[i])]] = i;
mmap[mp(x[i],y[i])] = -1;
}
}
for(auto & c : mmap){
if(c.second != -1)out[c.second] = m;
}
vector<int> res;
for(int i = 0 ; i < q ; ++i)res.pb(::res[i] + n);
return res;
}
#ifdef LOCAL
int main(int argc, char *argv[]) {
int N, C, Q;
scanf("%d%d%d", &N, &C, &Q);
std::vector<int> T(C), X(C), Y(C);
for(int i = 0; i < C; i++) {
scanf("%d%d%d", &T[i], &X[i], &Y[i]);
}
std::vector<int> W(Q), P(Q);
for(int i = 0; i < Q; i++) {
scanf("%d%d", &W[i], &P[i]);
}
auto res = simulateCollapse(N, T, X, Y, W, P);
for(auto i : res) {
printf("%d\n", i);
}
}
#endif
Compilation message
collapse.cpp: In member function 'void Dsurollback::rollback(int)':
collapse.cpp:30:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(data.size() > sz){
~~~~~~~~~~~~^~~~
collapse.cpp: In function 'void solve()':
collapse.cpp:68:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(qe < norm.size() && y[norm[qe]] == i)Dsu.Merge(x[norm[qe]] , y[norm[qe]]),++qe;
~~~^~~~~~~~~~~~~
collapse.cpp:69:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(qi < q.size() && p[q[qi]] == i){
~~~^~~~~~~~~~
collapse.cpp:85:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(qe < norm.size() && x[norm[qe]] == i)Dsu.Merge(x[norm[qe]] , y[norm[qe]]),++qe;
~~~^~~~~~~~~~~~~
collapse.cpp:86:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(qi < q.size() && p[q[qi]] == i - 1){
~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
3320 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
2936 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
34 ms |
6644 KB |
Output is correct |
| 2 |
Incorrect |
36 ms |
6648 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
36 ms |
6640 KB |
Output is correct |
| 2 |
Incorrect |
36 ms |
6516 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
3320 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
2936 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
