#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const int B = 350;
#define all(x) x.begin(),x.end()
#define sz(x) x.size()
#define X first
#define Y second
typedef pair<int,int> ii;
typedef vector<int> vi;
struct Edge {
int x, y, i;
bool operator < (const Edge &a) const {
return x < a.x;
}
};
struct Ques {
int day, typ;
int idx, num;
bool operator < (const Ques &a) const {
return day == a.day ? typ : day < a.day;
}
};
namespace DSU {
int p[N];
int s[N];
int init() {
iota(p,p + N,0);
fill(s,s + N,1);
}
int lead(int x) {
return p[x] == x ? x : p[x] = lead(p[x]);
}
int join(int x,int y) {
x = lead(x);
y = lead(y);
if (x == y) return 0;
if (s[x] < s[y]) swap(x,y);
p[y] = x;
s[x] += s[y];
return 1;
}
};
bool isOn[N], usedv[N], usede[N];
vector<Edge> E, se1, se2;
vector<int> ans;
int n, m;
void calc(vector<Ques> qr) {
fill(usedv,usedv + N,0);
fill(usede,usede + N,0);
map<int,vector<ii>> mp;
vector<Ques> Q;
vector<Edge> ed;
vector<int> vx;
for(Ques q : qr) {
if (q.typ) usede[q.idx] = usedv[E[q.idx].x] = usedv[E[q.idx].y] = 1;
else Q.push_back(q);
}
for(int i = 0 ; i < n ; ++i) if (usedv[i]) vx.push_back(i);
for(int i = 0 ; i < m ; ++i) if (usede[i]) ed.push_back(E[i]);
sort(all(Q),[](Ques &a,Ques &b) {
return a.num < b.num;
});
for(int t = 0 ; t < 2 ; ++t) {
DSU::init();
for(int i = 0, j = 0, r = 0 ; i < sz(Q) ; ++i) {
while (j < se1.size()) {
if (t == 0 && se1[j].x > Q[i].num) break;
if (t == 1 && se1[j].x <= Q[i].num) break;
if (!usede[se1[j].i] && isOn[se1[j].i])
r += DSU::join(se1[j].x,se1[j].y);
j++;
}
ans[Q[i].idx] -= r;
for(int x : vx) {
if (t == 0 && x > Q[i].num) continue;
if (t == 1 && x <= Q[i].num) continue;
mp[Q[i].idx].push_back({x,DSU::lead(x)});
}
}
reverse(Q.begin(),Q.end());
swap(se1,se2);
}
for(Ques q : qr) {
if (q.typ) isOn[q.idx] ^= 1;
else {
for(ii t : mp[q.idx]) DSU::p[t.X] = t.Y;
for(Edge e : ed)
if (isOn[e.i] && (e.x <= q.num || e.y > q.num))
ans[q.idx] -= DSU::join(e.x,e.y);
}
}
}
vi simulateCollapse(int _,vi T,vi X,vi Y,vi W,vi P) {
n = _;
m = T.size();
vector<Ques> v;
map<ii,int> mp;
for(int i = 0 ; i < m ; i++) {
if (X[i] < Y[i]) swap(X[i], Y[i]);
int num;
if(!mp.count({X[i],Y[i]})) {
mp[{X[i],Y[i]}] = num = sz(E);
se1.push_back({X[i],Y[i],num});
se2.push_back({Y[i],X[i],num});
E.push_back({X[i],Y[i],num});
}
else num = mp[{X[i],Y[i]}];
v.push_back({i,1,num,0});
}
sort(all(se1));
sort(all(se2)); reverse(all(se2));
ans.assign(W.size(),n);
for(int i = 0 ; i < W.size() ; ++i)
v.push_back({W[i],0,i,P[i]});
sort(all(v));
for(int i = 0 ; i < v.size() ; i += B)
calc(vector<Ques>(v.begin() + i,v.begin() + min((int)v.size(),i + B)));
return ans;
}
Compilation message
collapse.cpp: In function 'int DSU::init()':
collapse.cpp:37:5: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
collapse.cpp: In function 'void calc(std::vector<Ques>)':
collapse.cpp:82:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0, j = 0, r = 0 ; i < sz(Q) ; ++i) {
^
collapse.cpp:83:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (j < se1.size()) {
~~^~~~~~~~~~~~
collapse.cpp: In function 'vi simulateCollapse(int, vi, vi, vi, vi, vi)':
collapse.cpp:136:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0 ; i < W.size() ; ++i)
~~^~~~~~~~~~
collapse.cpp:136:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for(int i = 0 ; i < W.size() ; ++i)
^~~
collapse.cpp:139:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
sort(all(v));
^~~~
collapse.cpp:141:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0 ; i < v.size() ; i += B)
~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
1908 KB |
Output is correct |
| 2 |
Runtime error |
525 ms |
524288 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
140 ms |
5608 KB |
Output is correct |
| 2 |
Correct |
147 ms |
5664 KB |
Output is correct |
| 3 |
Correct |
461 ms |
10488 KB |
Output is correct |
| 4 |
Incorrect |
152 ms |
5736 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
139 ms |
5608 KB |
Output is correct |
| 2 |
Runtime error |
564 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
1908 KB |
Output is correct |
| 2 |
Runtime error |
525 ms |
524288 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
