#include <bits/stdc++.h>
#include "werewolf.h"
#define debug(x) cerr << #x << " " << x << "\n"
#define debug_with_space(x) cerr << #x << " " << x << " "
using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <ll, pii> piii;
const ll NMAX = 400001;
const int INF = 2e9;
const ll MOD = 998244353;
const ll p = 31;
const ll BLOCK = 101;
const ll nr_of_bits = 18;
vector <int> init[NMAX];
class Arbore {
int parent[NMAX];
vector <int> v[NMAX];
int stamp = 0;
public:
pii timp[NMAX];
int dp[NMAX][nr_of_bits];
vector <int> parcurgere;
int n;
void Init(int _n) {
n = _n;
parcurgere.push_back(0);
for(int i = 0; i <= n + 1; i++) {
parent[i] = 0;
}
}
int root(int x) {
if(parent[x] == 0)
return x;
return (parent[x] = root(parent[x]));
}
void merge(int a, int b) {
a = root(a);
if(a == b)
return;
parent[a] = b;
v[a].push_back(b);
v[b].push_back(a);
}
void DFS(int node, int p) {
timp[node].first = ++stamp;
dp[node][0] = p;
parcurgere.push_back(node);
for(auto x : v[node]) {
if(x == p)
continue;
DFS(x, node);
}
timp[node].second = stamp;
}
void Precalc() {
for(int j = 1; j < nr_of_bits; j++) {
for(int i = 1; i <= n; i++) {
dp[i][j] = dp[dp[i][j - 1]][j - 1];
}
}
}
} C, D;
class AIB{
int aib[NMAX], n;
public:
void Init(int _n){
n = _n + 1;
}
void update(int x){
for(int i = x; i < n; i += i&(-i)){
aib[i]++;
}
}
int query(int x){
int s = 0;
for(int i = x; i > 0; i -= i&(-i)){
s += aib[i];
}
return s;
}
}aib;
vector <pii> queries[NMAX];
vector <int> Compute(int Q) {
vector <int> rez(Q);
map <int, int> mp;
for(int i = 1; i < D.parcurgere.size(); i++){
mp[D.parcurgere[i]] = i;
//debug_with_space(D.parcurgere[i]);
}
//debug(Q);
aib.Init(D.n);
int i;
for(int i = 1; i <= C.n; i++){
aib.update(mp[C.parcurgere[i]]);
// debug(mp[C.parcurgere[i]]);
for(auto x : queries[i]){
int c = x.second;
if(c < 0)
c = -1;
else
c = 1;
rez[c * x.second] += c * aib.query(x.first);
}
}
for(i = 0; i < Q; i++){
rez[i] = (rez[i] > 0);
}
return rez;
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
int Q = S.size();
vector<int> A(Q);
int i;
for(i = 0; i < X.size(); i++) {
init[X[i] + 1].push_back(Y[i] + 1);
init[Y[i] + 1].push_back(X[i] + 1);
}
C.Init(N);
D.Init(N);
for(int i = N; i >= 1; i--) {
for(auto x : init[i]) {
if(x > i) {
C.merge(x, i);
// break;
}
}
}
for(int i = 1; i <= N; i++) {
for(auto x : init[i]) {
if(x < i) {
D.merge(x, i);
// break;
}
}
}
C.DFS(1, 0);
//debug(N);
D.DFS(N, 0);
C.Precalc();
D.Precalc();
for(i = 0; i < Q; i++) {
S[i]++;
R[i]++;
E[i]++;
L[i]++;
int r = S[i], pas = nr_of_bits - 1;
while(pas >= 0) {
int nou = C.dp[r][pas];
if(nou != 0 && nou >= L[i])
r = nou;
pas--;
}
pii a = {C.timp[r].first, C.timp[r].second};
r = E[i], pas = nr_of_bits - 1;
while(pas >= 0) {
int nou = D.dp[r][pas];
if(nou != 0 && nou <= R[i])
r = nou;
pas--;
}
pii b = {D.timp[r].first, D.timp[r].second};
int x1 = a.first, x2 = a.second, y1 = b.first, y2 = b.second;
queries[x1 - 1].push_back({y1 - 1, i});
queries[x1 - 1].push_back({y2, -i});
queries[x2].push_back({y2, i});
queries[x2].push_back({y1 - 1, -i});
}
A = Compute(Q);
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();
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();
}
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;
}
*/
Compilation message
werewolf.cpp: In function 'std::vector<int> Compute(int)':
werewolf.cpp:95:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
95 | for(int i = 1; i < D.parcurgere.size(); i++){
| ~~^~~~~~~~~~~~~~~~~~~~~
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:126:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
126 | for(i = 0; i < X.size(); i++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
50532 KB |
Output is correct |
| 2 |
Correct |
30 ms |
50540 KB |
Output is correct |
| 3 |
Correct |
31 ms |
50540 KB |
Output is correct |
| 4 |
Correct |
30 ms |
50444 KB |
Output is correct |
| 5 |
Incorrect |
30 ms |
50532 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
50532 KB |
Output is correct |
| 2 |
Correct |
30 ms |
50540 KB |
Output is correct |
| 3 |
Correct |
31 ms |
50540 KB |
Output is correct |
| 4 |
Correct |
30 ms |
50444 KB |
Output is correct |
| 5 |
Incorrect |
30 ms |
50532 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1123 ms |
142724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
50532 KB |
Output is correct |
| 2 |
Correct |
30 ms |
50540 KB |
Output is correct |
| 3 |
Correct |
31 ms |
50540 KB |
Output is correct |
| 4 |
Correct |
30 ms |
50444 KB |
Output is correct |
| 5 |
Incorrect |
30 ms |
50532 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
