#include <bits/stdc++.h>
#include "collapse.h"
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef pair<int, int> ii;
const int len = 1e3;//1e5+5;
int n, m, q;
struct segment_tree{
int tree[4*len];
segment_tree(){}
void build(int p, int l, int r, int t){
if (l == r){
if (t == 0)
tree[p] = l+1;
else
tree[p] = n-l;
}
else{
tree[p] = 0;
int mid = (l+r)/2;
build(2*p, l, mid, t);
build(2*p+1, mid+1, r, t);
}
}
void prop(int p, int l, int r){
if (!tree[p] || l == r) return;
tree[2*p] += tree[p];
tree[2*p+1] += tree[p];
tree[p] = 0;
}
void upd(int p, int l, int r, int i, int j, int x){
prop(p, l, r);
if (r < i || j < l)
return;
if (i <= l && r <= j)
tree[p] += x;
else{
int mid = (l+r)/2;
upd(2*p, l, mid, i, j, x);
upd(2*p+1, mid+1, r, i, j, x);
}
}
int ask(int p, int l, int r, int i){
prop(p, l, r);
if (l == r)
return tree[p];
int mid = (l+r)/2;
if (i <= mid)
return ask(2*p, l, mid, i);
return ask(2*p+1, mid+1, r, i);
}
};
segment_tree pref, suf;
int out[len], sz[len], par[len];
vector<ii> oper[4*len], st, todo[len];
map<ii, int> mym;
int fin(int i){
if (par[i] == i) return i;
return fin(par[i]);
}
void print(segment_tree cur){
for (int i = 0; i < n; i++)
printf("%d ", cur.ask(1, 0, n-1, i));
printf("\n");
}
void join(int i, int j){
if (sz[i] > sz[j])
par[j] = i, sz[i] += sz[j];
else
par[i] = j, sz[j] += sz[i];
}
void split(int i, int j){
if (sz[i] > sz[j])
par[j] = j, sz[i] -= sz[j];
else
par[i] = i, sz[j] -= sz[i];
}
void add(int p, int l, int r, int i, int j, ii v){
if (r < i || j < l)
return;
if (i <= l && r <= j)
oper[p].pb(v);
else{
int mid = (l+r)/2;
add(2*p, l, mid, i, j, v);
add(2*p+1, mid+1, r, i, j, v);
}
}
void solve(int p, int l, int r){
for (int i = 0; i < oper[p].size(); i++){
int a = oper[p][i].fi, b = oper[p][i].se, x = fin(a), y = fin(b);
if (x == y){
oper[p][i].fi = -1;
}
else{
pref.upd(1, 0, n-1, b, n-1, -1);
suf.upd(1, 0, n-1, 0, a, -1);
st.pb(mp(x, y));
join(x, y);
}
}
if (l == r){
for (int i = 0; i < todo[l].size(); i++){
int j = todo[l][i].fi, d = todo[l][i].se;
out[d] = pref.ask(1, 0, n-1, j)+suf.ask(1, 0, n-1, j+1);
}
//printf("time = %d\n", l);
//printf("pref = "), print(pref);
//printf("suf = "), print(suf);
}
else{
int mid = (l+r)/2;
solve(2*p, l, mid);
solve(2*p+1, mid+1, r);
}
for (int i = (int)oper[p].size()-1; i >= 0; i--){
if (oper[p][i].fi == -1)
continue;
int a = oper[p][i].fi, b = oper[p][i].se;
pref.upd(1, 0, n-1, b, n-1, 1);
suf.upd(1, 0, n-1, 0, a, 1);
split(st.back().fi, st.back().se);
st.pop_back();
}
oper[p].clear();
}
/*vector<int> adj[len];
int vis[len], nex[len];
void dfs(int u){
vis[u] = 1;
for (int j = 0; j < adj[u].size(); j++){
int v = adj[u][j];
if (!vis[v])
dfs(v);
}
}*/
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++)
if (X[i] > Y[i])
swap(X[i], Y[i]);
for (int i = 0; i < m; i++){
if (T[i] == 1)
continue;
nex[i] = m-1;
for (int j = i+1; j < m; j++)
if (mp(X[i], Y[i]) == mp(X[j], Y[j])){
nex[i] = j-1;
break;
}
}
vector<int> out3(q, 0);
for (int i = 0; i < q; i++){
int d = W[i], p = P[i];
for (int j = 0; j < n; j++)
adj[j].clear(), vis[j] = 0;
for (int j = 0; j < m; j++){
if (T[j] == 0 && j <= d && nex[j] >= d && (Y[j] <= p || X[j] >= p+1))
adj[X[j]].pb(Y[j]), adj[Y[j]].pb(X[j]);
}
out3[i] = 0;
for (int j = 0; j < n; j++)
if (!vis[j])
out3[i]++, dfs(j);
}
return out3;*/
pref.build(1, 0, n-1, 0);
suf.build(1, 0, n-1, 1);
for (int i = 0; i < n; i++){
par[i] = i;
sz[i] = 1;
}
for (int i = 0; i < m; i++){
todo[i].clear();
}
mym.clear();
for (int i = 0; i < m; i++){
int t = T[i], x = X[i], y = Y[i];
if (x > y)
swap(x, y);
if (t == 0)
mym[mp(x, y)] = i;
else{
add(1, 0, m-1, mym[mp(x, y)], i-1, mp(x, y));
mym.erase(mp(x, y));
}
}
for (auto &it: mym)
add(1, 0, m-1, it.se, m-1, it.fi);
for (int i = 0; i < q; i++){
int d = W[i], p = P[i];
todo[d].pb(mp(p, i));
}
solve(1, 0, m-1);
vector<int> out2(q, 0);
for (int i = 0; i < q; i++)
out2[i] = out[i];
return out2;
}
/*
4 2 2
0 0 1
0 2 3
0 0
1 2
100 8 6
0 3 99
0 2 1
0 5 98
1 99 3
0 40 80
0 30 80
1 80 30
1 1 2
7 8
7 98
0 38
4 50
2 12
6 90
*/
Compilation message
collapse.cpp: In function 'void solve(int, int, int)':
collapse.cpp:112:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < oper[p].size(); i++){
~~^~~~~~~~~~~~~~~~
collapse.cpp:126:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < todo[l].size(); i++){
~~^~~~~~~~~~~~~~~~
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:240:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for (int i = 0; i < q; i++)
^~~
collapse.cpp:242:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
return out2;
^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
1152 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
21 ms |
5748 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
20 ms |
5748 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
1152 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
