#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 = a, r0 = b;
while(l0 < r0){
ll mid = (l0 + r0 + 1) >> 1;
if(get(1, 1, n, a, mid, true) < l[i])
r0 = mid - 1;
else
l0 = mid;
}
p1 = l0;
l0 = a, r0 = b;
while(l0 < r0){
ll mid = (l0 + r0) >> 1;
if(get(1, 1, n, a, mid, false) > r[i])
l0 = mid + 1;
else
r0 = mid;
}
p2 = l0;
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 1
0 2
1 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 |
8280 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 |
8280 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
814 ms |
40648 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
6232 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
8280 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
