#include <bits/stdc++.h>
#include "collapse.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
const int K = 450;
const int N = (int)1e5 + 5;
int n;
bool active[N];
bool change[N];
struct query{
int type;
int time;
int xx;
int id;
bool operator< (const query &qi) const {
if(time == qi.time)
return type < qi.type;
return time < qi.time;
}
};
int par[N];
int sub[N];
vector<pii> rev;
int fin(int x){
if(par[x] == x) return x;
return par[x]=fin(par[x]);
}
int total;
void unite(int u, int v, bool keep){
u = fin(u);
v = fin(v);
if(u == v) return;
total ++ ;
if(sub[u] > sub[v]) swap(u, v);
sub[v] += sub[u];
if(keep)
rev.push_back(mp(u, v));
}
vector<int> simulateCollapse(int _N, vector<int> T, vector<int> X, vector<int> Y, vector<int> W, vector<int> P) {
n = _N;
vector<query> qq;
vector<pii> E;
for(int i = 0 ; i < T.size(); i ++ ){
if(X[i] > Y[i]) swap(X[i], Y[i]);
E.push_back(mp(X[i], Y[i]));
}
sort(E.begin(), E.end());
E.resize(unique(E.begin(), E.end()) - E.begin());
int m = E.size();
int id;
for(int i = 0 ; i < X.size(); i ++ ){
id = lower_bound(E.begin(), E.end(), mp(X[i], Y[i])) - E.begin();
X[i] = id;
}
vector<query> qaq;
for(int i = 0 ; i < T.size(); i ++ ){
qaq.push_back({0, i, X[i], 0});
}
for(int i = 0 ; i < W.size(); i ++ ){
qaq.push_back({1, W[i], P[i], i});
}
sort(qaq.begin(), qaq.end());
vector<int> soln(W.size(), n);
int li = 0;
int ri;
int pp;
while(li < qaq.size()){
ri = min((int)qaq.size() - 1, li + K - 1);
for(int i = 0 ; i < m ; i ++ ){
change[i] = false;
}
for(int i = 0 ; i < n; i ++ ){
par[i] = i;
sub[i] = 1;
}
for(int j = li ; j <= ri; j ++ ){
if(qaq[j].type == 0){
change[qaq[j].xx] = true;
}
}
vector<pii> res;
vector<int> chk;
for(int i = 0 ; i < m ; i ++ ){
if(change[i] == false && active[i]){
res.push_back(mp(E[i].se, E[i].fi));
}
else{
if(change[i]){
chk.push_back(i);
}
}
}
// !!!!!!!!!!!!!!!!!!!1
sort(res.begin(), res.end());
vector<pii> ord;
for(int j = li ; j <= ri ;j ++ ){
if(qaq[j].type == 1){
ord.push_back(mp(qaq[j].xx, j));
}
}
sort(ord.begin(), ord.end());
pp = 0;
total = 0;
for(auto &x : ord){
while(pp < res.size() && res[pp].fi <= x.fi){
unite(res[pp].fi, res[pp].se, false);
pp ++ ;
}
for(int j = li ; j < x.se; j ++ ){
if(qaq[j].type == 0){
active[qaq[j].xx] ^= 1;
}
}
for(auto y : chk){
if(active[y] && E[y].se <= x.fi)
unite(E[y].fi, E[y].se, true);
}
soln[qaq[x.se].id] -= total;
while(!rev.empty()){
total -- ;
sub[rev.back().se] -= sub[rev.back().fi];
par[rev.back().fi] = rev.back().fi;
rev.pop_back();
}
for(int j = li ; j < x.se; j ++ ){
if(qaq[j].type == 0)active[qaq[j].xx] ^= 1;
}
}
// #############################
for(auto &x : res){
swap(x.fi, x.se);
}
sort(res.begin(), res.end());
reverse(res.begin(), res.end());
reverse(ord.begin(), ord.end());
for(int i = 0 ; i < n; i ++ ){
par[i] = i;
sub[i] = 1;
}
pp = 0;
total = 0;
for(auto x : ord){
while(pp < res.size() && res[pp].fi > x.fi){
unite(res[pp].fi, res[pp].se, false);
pp ++ ;
}
for(int j = li ; j < x.se; j ++ ){
if(qaq[j].type == 0)active[qaq[j].xx] ^= 1;
}
for(auto y : chk){
if(active[y] && E[y].fi > x.fi)
unite(E[y].fi, E[y].se, true);
}
soln[qaq[x.se].id] -= total;
while(!rev.empty()){
total -- ;
sub[rev.back().se] -= sub[rev.back().fi];
par[rev.back().fi] = rev.back().fi;
rev.pop_back();
}
for(int j = li ; j < x.se; j ++ ){
if(qaq[j].type == 0)active[qaq[j].xx] ^= 1;
}
}
// #############################
for(int j = li; j <= ri; j ++ ){
if(qaq[j].type == 0){
active[qaq[j].xx] ^= 1;
}
}
li += K;
}
return soln;
}
Compilation message
collapse.cpp: In function 'std::vector<int> simulateCollapse(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
collapse.cpp:62:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | for(int i = 0 ; i < T.size(); i ++ ){
| ~~^~~~~~~~~~
collapse.cpp:70:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | for(int i = 0 ; i < X.size(); i ++ ){
| ~~^~~~~~~~~~
collapse.cpp:75:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | for(int i = 0 ; i < T.size(); i ++ ){
| ~~^~~~~~~~~~
collapse.cpp:78:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | for(int i = 0 ; i < W.size(); i ++ ){
| ~~^~~~~~~~~~
collapse.cpp:86:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
86 | while(li < qaq.size()){
| ~~~^~~~~~~~~~~~
collapse.cpp:124:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
124 | while(pp < res.size() && res[pp].fi <= x.fi){
| ~~~^~~~~~~~~~~~
collapse.cpp:162:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
162 | while(pp < res.size() && res[pp].fi > x.fi){
| ~~~^~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
12 ms |
972 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
588 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
129 ms |
4356 KB |
Output is correct |
| 2 |
Correct |
128 ms |
4372 KB |
Output is correct |
| 3 |
Incorrect |
297 ms |
10676 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
127 ms |
4392 KB |
Output is correct |
| 2 |
Incorrect |
133 ms |
4408 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
12 ms |
972 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
588 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
