#include "werewolf.h"
#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <cmath>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#include <numeric>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <bitset>
#include <cstring>
#include <unordered_map>
using namespace std;
typedef int ll;
vector<ll> d[200007];
bool used1[200007], used2[200007];
ll lim = 0;
void dfs1(ll v){
if(v < lim)
return;
used1[v] = true;
for(auto i: d[v]){
if(!used1[i] && i >= lim)
dfs1(i);
}
}
void dfs2(ll v){
if(v > lim)
return;
used2[v] = true;
for(auto i: d[v]){
if(!used2[i] && i <= lim)
dfs2(i);
}
}
vector<ll> ord;
void dfs(ll v, ll par){
ord.push_back(v);
for(auto i: d[v])
if(i != par)
dfs(i, v);
}
ll a[200007];
pair<ll, ll> t[800007];
void build(ll v, ll l, ll r){
if(l == r){
t[v] = {a[l], a[l]};
return;
}
ll mid = (l + r) >> 1;
build(2 * v, l, mid);
build(2 * v + 1, mid + 1, r);
t[v].first = min(t[2 * v].first, t[2 * v + 1].first);
t[v].second = max(t[2 * v].second, t[2 * v + 1].second);
}
ll get(ll v, ll l, ll r, ll ql, ll qr, bool mn){
if(r < ql || qr < l)
return (mn ? (ll)(1e9) : (ll)(-1e9));
if(ql <= l && r <= qr)
return (mn ? t[v].first : t[v].second);
ll mid = (l + r) >> 1;
if(mn)
return min(get(2 * v, l, mid, ql, qr, mn), get(2 * v + 1, mid + 1, r, ql, qr, mn));
return max(get(2 * v, l, mid, ql, qr, mn), get(2 * v + 1, mid + 1, r, ql, qr, mn));
}
std::vector<int> check_validity(int n, std::vector<int> x, std::vector<int> y,
std::vector<int> s, std::vector<int> e,
std::vector<int> l, std::vector<int> r) {
ll q = l.size();
for(int i = 0; i < x.size(); i++){
d[x[i]].push_back(y[i]);
d[y[i]].push_back(x[i]);
}
vector<int> ans;
if(x.size() == n - 1){
for(int i = 0; i < n; i++){
if(d[i].size() == 1){
dfs(i, -1);
break;
}
}
vector<ll> pos(n + 1);
for(int i = 0; i < n; i++){
a[i + 1] = ord[i] + 1;
pos[a[i + 1]] = i + 1;
}
for(int i = 0; i < q; i++)
s[i]++, e[i]++, l[i]++, r[i]++;
build(1, 1, n);
for(int i = 0; i < q; i++){
ll a = pos[s[i]], b = pos[e[i]];
ll p1 = 0, p2 = 0;
ll l0 = 1, r0 = n;
while(l0 < r0){
ll mid = (l0 + r0 + 1) >> 1;
ll pos = 0;
if(a < b)
pos = a + mid - 1;
else
pos = a - mid + 1;
if(get(1, 1, n, min(a, pos), max(a, pos), true) < l[i]){
r0 = mid - 1;
}
else
l0 = mid;
}
if(a < b)
p1 = a + l0 - 1;
else
p1 = a - l0 + 1;
l0 = 1, r0 = n;
while(l0 < r0){
ll mid = (l0 + r0 + 1) >> 1;
ll pos = 0;
if(a < b)
pos = b - mid + 1;
else
pos = b + mid - 1;
if(get(1, 1, n, min(b, pos), max(b, pos), false) > r[i]){
r0 = mid - 1;
}
else
l0 = mid;
}
if(a < b)
p2 = b - l0 + 1;
else
p2 = b + l0 - 1;
// cout << l0 << endl;
// cout << p1 << ' ' << p2 << endl;
// cout << get(1, 1, n, 1, n, true) << endl;
if(a < b){
if(p1 >= p2)
ans.push_back(1);
else
ans.push_back(0);
}
else{
if(p1 <= p2)
ans.push_back(1);
else
ans.push_back(0);
}
}
return ans;
}
for(int i = 0; i < q; i++){
lim = l[i];
dfs1(s[i]);
lim = r[i];
dfs2(e[i]);
int res = 0;
for(int j = 0; j < n; j++){
if(used1[j] && used2[j]){
res = 1;
}
used1[j] = used2[j] = 0;
}
ans.push_back(res);
}
return ans;
}
/*
6 6 3
0 3
3 1
3 4
1 2
2 5
1 5
4 2 1 2
4 2 2 2
5 4 3 4
*/
/*
6 6 1
0 3
3 1
3 4
1 2
2 5
1 5
4 2 1 2
4 2 2 2
5 4 3 4
*/
/*
4 3 1
3 0
0 1
1 2
3 2 2 2
*/
/*
4 3 1
3 1
1 0
2 0
3 2 1 2
*/
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:99:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
99 | for(int i = 0; i < x.size(); i++){
| ~~^~~~~~~~~~
werewolf.cpp:106:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
106 | if(x.size() == n - 1){
| ~~~~~~~~~^~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
6232 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
8284 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
6232 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
8284 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1506 ms |
40756 KB |
Output is correct |
| 2 |
Correct |
1329 ms |
49348 KB |
Output is correct |
| 3 |
Correct |
1381 ms |
49092 KB |
Output is correct |
| 4 |
Correct |
1430 ms |
49356 KB |
Output is correct |
| 5 |
Correct |
1450 ms |
49096 KB |
Output is correct |
| 6 |
Correct |
1475 ms |
49160 KB |
Output is correct |
| 7 |
Correct |
1635 ms |
48940 KB |
Output is correct |
| 8 |
Correct |
1349 ms |
49052 KB |
Output is correct |
| 9 |
Correct |
1172 ms |
49080 KB |
Output is correct |
| 10 |
Correct |
1315 ms |
49128 KB |
Output is correct |
| 11 |
Correct |
1368 ms |
49020 KB |
Output is correct |
| 12 |
Correct |
1291 ms |
48948 KB |
Output is correct |
| 13 |
Correct |
1609 ms |
49096 KB |
Output is correct |
| 14 |
Correct |
1614 ms |
49072 KB |
Output is correct |
| 15 |
Correct |
1642 ms |
49044 KB |
Output is correct |
| 16 |
Correct |
1625 ms |
49144 KB |
Output is correct |
| 17 |
Correct |
1495 ms |
49108 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
6232 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
8284 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
