#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> adj[200005];
vector<int> ladj[400005], radj[400005];
int pl[400005], pr[400005];
int pls, prs, cur;
int llabel[400005], rlabel[400005];
pair<int, int> rngl[400005], rngr[400005];
int fenw[400005];
bool vis[400005];
int qr(int x) {
int s = 0;
for(;x;x-=x&-x) s += fenw[x];
return s;
}
void upd(int x) {
for(;x<=400000;x+=x&-x) fenw[x]++;
}
int fpar(int *parr, int x) {
return parr[x] == x ? x : (parr[x] = fpar(parr, parr[x]));
}
void dfs(vector<int>* adj, pair<int, int>* rngarr, int *lab, int x) {
rngarr[x].first = cur;// cout << x << ' ';
if(adj[x].empty()){lab[x] = cur; rngr[cur].second=cur++; return;}
for(int e:adj[x]) dfs(adj, rngarr, lab, e);
rngarr[x].second = cur-1;
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
for(int i=0;i<=400000;i++) pl[i] = pr[i] = i;
int Q = S.size(); pls = prs = N;
vector<int> A(Q, 0);
vector<pair<int, int>> ls(Q), rs(Q);
vector<int> lnode(Q), rnode(Q);
for(int i=0;i<Q;i++) ls[i] = {L[i], i};
for(int i=0;i<Q;i++) rs[i] = {R[i], i};
for(int i=0;i<N;i++) ls.emplace_back(i, INT_MAX), rs.emplace_back(i, INT_MIN);
sort(ls.rbegin(), ls.rend()); sort(rs.begin(), rs.end());
vector<pair<int, int>> points;
for(int i=0;i<X.size();i++) {
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
for(auto e:ls) {
if(e.second == INT_MAX) { //merge
ladj[pls].push_back(e.first); pl[e.first] = pls;
for(int E:adj[e.first]) {
if(E <= e.first) continue;
if(fpar(pl, E) == pls) continue;
ladj[pls].push_back(fpar(pl, E));
pl[fpar(pl, E)] = pls;
}
pls++;
} else {
lnode[e.second] = fpar(pl, S[e.second]);
}
}
for(auto e:rs) {
if(e.second == INT_MIN) { //merge
radj[prs].push_back(e.first); pr[e.first] = prs;
for(int E:adj[e.first]) {
if(E >= e.first) continue;
if(fpar(pr, E) == prs) continue;
radj[prs].push_back(fpar(pr, E));
pr[fpar(pr, E)] = prs;
}
prs++;
} else {
rnode[e.second] = fpar(pr, E[e.second]);
}
} pls--; prs--; //pls, prs == root of left and right respectively
//for(int i=0;i<=pls;i++) {cout << i << ": "; for(int e:ladj[i]) cout << e << ' '; cout << '\n';}
cur = 1; dfs(ladj, rngl, llabel, pls);
cur = 1; dfs(radj, rngr, rlabel, prs);
for(int i=0;i<N;i++) points.emplace_back(llabel[i], rlabel[i]);
for(int i=0;i<Q;i++) points.emplace_back(rngl[lnode[i]].first-1, N+i+1), points.emplace_back(rngl[lnode[i]].second, N+i+1);
//cout << "Helhloe";
sort(points.begin(), points.end());
for(auto e:points) {
if(e.second > N) {
int ci = e.second-N-1; //query number
A[ci] += (vis[ci] ? 1 : -1) * (qr(rngr[rnode[ci]].second) - qr(rngr[rnode[ci]].first-1));
vis[ci] = 1; A[ci] = min(A[ci], 1);
} else {
upd(e.second);
}
}
return A;
}
/*
namespace {
int read_int() {
int x;
if (scanf("%d", &x) != 1) {
fprintf(stderr, "Error while reading input\n");
exit(1);
}
return x;
}
} // namespace
int main() {
int N = read_int();
int M = read_int();
int Q = read_int();
std::vector<int> X(M), Y(M), S(Q), E(Q), L(Q), R(Q);
for (int j = 0; j < M; ++j) {
X[j] = read_int();
Y[j] = read_int();
}
for (int i = 0; i < Q; ++i) {
S[i] = read_int();
E[i] = read_int();
L[i] = read_int();
R[i] = read_int();
}
std::vector<int> A = check_validity(N, X, Y, S, E, L, R);
for (size_t i = 0; i < A.size(); ++i) {
printf("%d\n", A[i]);
}
return 0;
}
*/
/*
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
*/
Compilation message
werewolf.cpp: In function 'void dfs(std::vector<int>*, std::pair<int, int>*, int*, int)':
werewolf.cpp:30:56: warning: operation on 'cur' may be undefined [-Wsequence-point]
30 | if(adj[x].empty()){lab[x] = cur; rngr[cur].second=cur++; return;}
| ~~~^~
werewolf.cpp:30:56: warning: operation on 'cur' may be undefined [-Wsequence-point]
werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:46:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | for(int i=0;i<X.size();i++) {
| ~^~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
18 ms |
26964 KB |
Output is correct |
| 2 |
Correct |
14 ms |
26964 KB |
Output is correct |
| 3 |
Correct |
14 ms |
26964 KB |
Output is correct |
| 4 |
Correct |
14 ms |
26944 KB |
Output is correct |
| 5 |
Correct |
14 ms |
26964 KB |
Output is correct |
| 6 |
Correct |
15 ms |
26988 KB |
Output is correct |
| 7 |
Incorrect |
14 ms |
26992 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
18 ms |
26964 KB |
Output is correct |
| 2 |
Correct |
14 ms |
26964 KB |
Output is correct |
| 3 |
Correct |
14 ms |
26964 KB |
Output is correct |
| 4 |
Correct |
14 ms |
26944 KB |
Output is correct |
| 5 |
Correct |
14 ms |
26964 KB |
Output is correct |
| 6 |
Correct |
15 ms |
26988 KB |
Output is correct |
| 7 |
Incorrect |
14 ms |
26992 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
495 ms |
90200 KB |
Output is correct |
| 2 |
Correct |
398 ms |
94856 KB |
Output is correct |
| 3 |
Correct |
394 ms |
91764 KB |
Output is correct |
| 4 |
Correct |
432 ms |
90492 KB |
Output is correct |
| 5 |
Correct |
432 ms |
90436 KB |
Output is correct |
| 6 |
Correct |
479 ms |
90324 KB |
Output is correct |
| 7 |
Correct |
447 ms |
90260 KB |
Output is correct |
| 8 |
Correct |
394 ms |
94788 KB |
Output is correct |
| 9 |
Incorrect |
367 ms |
91848 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
18 ms |
26964 KB |
Output is correct |
| 2 |
Correct |
14 ms |
26964 KB |
Output is correct |
| 3 |
Correct |
14 ms |
26964 KB |
Output is correct |
| 4 |
Correct |
14 ms |
26944 KB |
Output is correct |
| 5 |
Correct |
14 ms |
26964 KB |
Output is correct |
| 6 |
Correct |
15 ms |
26988 KB |
Output is correct |
| 7 |
Incorrect |
14 ms |
26992 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
