#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
#define in insert
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second
template<typename T>
void mxx(T &a, T b){if(b > a) a = b;}
template<typename T>
void mnn(T &a, T b){if(b < a) a = b;}
pair<int, int> operator+(pair<int, int> a, pair<int, int> b) {
return make_pair(min(a.ff, b.ff), max(a.ss, b.ss));
}
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> ret(Q, 0), pos(n);
vector<vector<int>> g(n);
for(int i = 0; i < X.size(); i++) {
g[X[i]].pb(Y[i]);
g[Y[i]].pb(X[i]);
}
int st = 0;
for(int i = 0; i < n; i++) {
if(g[i].size() == 1) st = i;
}
vector<int> p;
int x = st, y = g[st][0];
p.pb(x);
while(g[y].size() == 2) {
p.pb(y);
x ^= g[y][0] ^ g[y][1];
swap(x, y);
}
p.pb(y);
vector<int> LOG(n + 10);
for(int i = 2; i < n + 10; i++) {
LOG[i] = LOG[i / 2] + 1;
}
vector<vector<pair<int, int>>> sp(n, vector<pair<int, int>>(20));
for(int i = 0; i < n; i++) {
sp[i][0] = {p[i], p[i]};
pos[p[i]] = i;
}
for(int i = 1; i < 20; i++) {
for(int j = 0; j < n; j++) {
if(j + (1 << i) > n) break;
sp[i][j] = sp[i][j - 1] + sp[i + (1 << (i - 1))][j - 1];
}
}
auto get = [&](int l, int r) -> pair<int, int> {
int id = LOG[r - l + 1];
return sp[l][id] + sp[r - (1 << id) + 1][id];
};
for(int i = 0; i < Q; i++) {
int s = S[i], e = E[i], l = L[i], r = R[i];
if(pos[s] > pos[e]) {
int ll = pos[e], rr = pos[s];
while(rr - ll > 1) {
int m = (rr + ll) / 2;
int mn = get(m, rr).ff;
if(mn < l) ll = m;
else rr = m;
}
int ans1 = ll + (p[i] < l);
ll = pos[e], rr = pos[s];
while(rr - ll > 1) {
int m = (rr + ll) / 2;
int mx = get(ll, m).ss;
if(mx > r) rr = m;
else ll = m;
}
int ans2 = rr - (p[i] > r);
if(ans2 >= ans1) ret[i] = 1;
} else {
int ll = pos[e], rr = pos[s];
while(rr - ll > 1) {
int m = (rr + ll) / 2;
int mn = get(ll, m).ff;
if(mn < l) rr = m;
else ll = m;
}
int ans1 = rr - (p[i] < l);
ll = pos[e], rr = pos[s];
while(rr - ll > 1) {
int m = (rr + ll) / 2;
int mx = get(m, rr).ss;
if(mx > r) ll = m;
else rr = m;
}
int ans2 = ll + (p[i] > r);
if(ans1 >= ans2) ret[i] = 1;
}
}
return ret;
}
Compilation message
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:25:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
25 | for(int i = 0; i < X.size(); i++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
328 ms |
127484 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
