#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T>
using matrix = vector<vector<T>>;
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) {
matrix<int> g(N);
for(int i = 0; i < X.size(); i++){
g[X[i]].push_back(Y[i]);
g[Y[i]].push_back(X[i]);
}
int Q = S.size();
std::vector<int> ans(Q);
if(false){
vector<int> c1(N), c2(N);
auto dfs =[&](int id, int l, int r,vector<int>&check, auto dfs)->void{
check[id] = 1;
for(int i : g[id]){
if(check[i] || i > r || i < l)
continue;
dfs(i,l,r,check,dfs);
}
};
for(int i = 0; i < Q; i++){
fill(all(c1),0);
fill(all(c2),0);
dfs(S[i],L[i],N,c1,dfs);
dfs(E[i],0,R[i],c2,dfs);
for(int j = 0; j < N; j++){
ans[i]|=c1[j]&&c2[j];
}
}
} else {
vector<int> v;
v.reserve(N);
auto dfs =[&](int id, int last, auto dfs)->void{
for(int i : g[id])
if(i != last) dfs(i,id,dfs);
v.push_back(id);
};
for(int i = 0; i < N; i++){
if(g[i].size() == 1){
dfs(i,-1,dfs);
break;
}
}
vector<int> inv(N);
for(int i = 0; i < N; i++)
inv[v[i]] = i;
matrix<int> smin(20,vector<int>(N)), smax(20,vector<int>(N));
for(int i = 0; i < N; i++)
smin[0][i] = v[i], smax[0][i] = v[i];
for(int i = 1; i < 20; i++){
for(int j = 0; j+(1<<i) <= N; i++){
smin[i][j] = min(smin[i-1][j],smin[i-1][j+(1<<i-1)]);
smax[i][j] = max(smax[i-1][j],smax[i-1][j+(1<<i-1)]);
}
}
auto qmin =[&](int l, int r){
int logg = log2(r-l+1);
return min(smin[logg][l],smin[logg][r-(1<<logg)+1]);
};
auto qmax =[&](int l, int r){
int logg = log2(r-l+1);
return max(smax[logg][l],smax[logg][r-(1<<logg)+1]);
};
for(int i = 0; i < Q; i++){
int a = inv[S[i]], b = inv[E[i]];
if(a < b){
int ini = a, fim = b;
while(ini!=fim){
//cout << 'a'<< ini << ' ' << fim << endl;
int m = (ini+fim+1)>>1;
if(qmin(a,m) >= L[i])
ini = m;
else fim = m-1;
}
//cout << "a->" << ini << '\n';
ans[i] = qmax(ini,b) <= R[i];
} else {
int ini = b, fim = a;
while(ini!=fim){
//cout <<'b'<< ini << ' ' << fim << endl;
int m = (ini+fim)>>1;
if(qmin(m,a) >= L[i])
fim = m;
else ini = m+1;
}
//cout << "b->" << ini << '\n';
ans[i] = qmax(b,ini) <= R[i];
}
}
}
return ans;
}
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:18:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
18 | for(int i = 0; i < X.size(); i++){
| ~~^~~~~~~~~~
werewolf.cpp:70:64: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
70 | smin[i][j] = min(smin[i-1][j],smin[i-1][j+(1<<i-1)]);
| ~^~
werewolf.cpp:71:64: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
71 | smax[i][j] = max(smax[i-1][j],smax[i-1][j+(1<<i-1)]);
| ~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
336 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
336 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
438 ms |
62136 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
336 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
