#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define MIN -1
#define MAX 1000000000
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define TAM 100000
typedef vector <int> vi;
vi querys, querys1;
vector <pair <int, int> > rangos, rangos1;
typedef long long int ll;
int v[2*TAM +10];
int v1[TAM+10];
int tree[4*TAM+10];
int tree1[4*TAM+10];
int ters[4*TAM+10];
int aux[2][4*TAM+10];
int n;
int vis1[3010], vis2[3010], vis[3*TAM+10];
vector <vi> G;
vector <vi> G1;
vector <int> v2;
void dfs(int x){
vis[x]=1;
v2.push_back(x);
for(int i=0;i<G[x].size ();i++){
if(vis[G1[x][i]]==0){
dfs(G1[x][i]);
}
}
}
void init(int node , int a, int b){
if(a==b){
tree[node]=v[a];
return ;
}
init(2*node,a,(a+b)/2);
init(2*node+1,(a+b)/2+1, b);
tree[node]=max(tree[2*node], tree[2*node+1]);
}
int query(int node, int a ,int b, int p ,int q){
if(q<a or b<p)return MIN;
if(p<=a and b<=q)return tree[node];
return max(query(2*node, a, (a+b)/2, p, q), query(2*node+1, (a+b)/2+1, b, p , q));
}
void init1 (int node, int a, int b){
if(a==b){
tree1[node]=v[a];
return ;
}
init1(2*node, a, (a+b)/2);
init1(2*node+1, (a+b)/2+1, b);
tree1[node]=min(tree1[2*node], tree1[2*node+1]);
}
int query1(int node, int a , int b, int p ,int q){
if(q<a or b<p)return MAX;
if(p<=a and b<=q)return tree1[node];
return min(query1(2*node, a, (a+b)/2, p, q), query1(2*node+1, (a+b)/2+1,b, p , q));
}
void dfs1(int x,int y){
vis1[x]=1;
for(int i=0;i<G[x].size();i++){
if(vis1[G[x][i]]==0 and G[x][i]>=y){
dfs1(G[x][i], y);
}
}
}
void dfs2(int x,int y){
vis2[x]=1;
for(int i=0;i<G[x].size();i++){
if(vis2[G[x][i]]==0 and G[x][i]<=y){
dfs2(G[x][i], y);
}
}
}
int binary(int s, int e, int L, int R){
if(s<e){
int l=s;
int r=e;
while(l<r){
int m=(l+r+1)/2;
if(query1(1, 0, n-1, l, m)<L)r=m-1;
else l=m;
}
if(query1(1, 0, n-1, s, l)>=L and query(1, 0, n-1, l, e)<= R)return 1;
else return 0;
} else {
int l=e;
int r=s;
while(l<r){
int m=(l+r)/2;
if (query1(1, 0, n-1, m,r)<L) l=m+1;
else r=m;
}
if (query1(1, 0, n-1, l, s)>=L and query(1, 0, n-1, e, l) <= R) return 1;
else return 0;
}
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y,vector<int> S, vector<int> E,vector<int> L, vector<int> R) {
n=N;
G=vector <vi>(n+1);
G1=vector <vi>(n+1);
for(int i=0;i<X.size ();i++){
G[X[i]].pb(Y[i]);
G[Y[i]].pb(X[i]);
G1[X[i]].pb(Y[i]);
G1[Y[i]].pb(X[i]);
}
int Q = S.size();
int sw1=0;
for(int i=0;i<n;i++){
if(G[i].size ()>=3){
sw1=1;
break;
}
}
vector <int> A(Q);
if(sw1==1 and X.size ()+1==n){
vector<int> A(Q);
for (int k = 0; k < Q; ++k) {
memset(vis1, 0, sizeof vis1);
memset(vis2, 0, sizeof vis2);
dfs1(S[k], L[k]);
dfs2(E[k], R[k]);
int sw=0;
for(int i=0;i<n;i++){
if(vis1[i]==1 and vis2[i]==1){
sw=1;
break;
}
}
A[k]=sw;
}
return A;
}
/*for(int i=0;i<n;i++){
if(G1[i].size ()==1){dfs(i);
break;}
}
map <int, int> m, m1;
for(int i=0;i<v2.size ();i++)v[i]=v2[i];
for(int i=0;i<v2.size ();i++){
m[v[i]]=i;
}
for(int i=0;i<v2.size ();i++)v1[i]=v2[i];
for(int i=0;i<v2.size ();i++)m1[v1[i]]=i;
init(0, 0, n-1);
init1(0, 0, n-1);
for(int k=0;k<Q;k++){int r1, r2;
r1=query(0, 0, n-1, min(m[S[k]],m[E[k]]), max(m[E[k]], m[S[k]]));
//rangos.pb(mp(min(m[S[k]],m[E[k]]), max(m[E[k]], m[S[k]])));
r2=query1(0, 0, n-1, (min(m1[S[k]],m1[E[k]])),(max(m1[E[k]], m1[S[k]])));
rangos1.pb(mp((min(m1[S[k]],m1[E[k]])),((max(m1[E[k]], m1[S[k]])))));
querys.pb(r1);
querys1.pb(r2);
int lobo=0, human=0;
if(r2>=L[k])human=1;
if(r1<=R[k])lobo=1;
if(human==1 and lobo==1)A[k]=1;
else{
if(m[r1]>=(n-1-m1[r2]))A[k]=1;
else A[k]=0;
}
}
return A;*/
for (int i=0;i<n;i++)aux[0][i]=aux[1][i]=-1;
for (int i=0;i<X.size();i++){
if (aux[0][X[i]] == -1) aux[0][X[i]] = Y[i];
else aux[1][X[i]] = Y[i];
if (aux[0][Y[i]] == -1) aux[0][Y[i]] = X[i];
else aux[1][Y[i]] = X[i];
}
int node;
for (node = 0; node < n; node++) if(aux[1][node]==-1) break;
v[0] = node;
ters[node] = 0;
v[1] = aux[0][node];
ters[aux[0][node]] = 1;
for (int i = 2; i < n; i++){
if (v[i-2] != aux[0][v[i-1]] and aux[0][v[i-1]] != -1){v[i] = aux[0][v[i-1]];
ters[aux[0][v[i-1]]] = i;}
else {v[i]=aux[1][v[i-1]];
ters[aux[1][v[i-1]]] = i;
}
}
init(1, 0, n-1);
init1(1, 0, n-1);
for(int k=0;k<Q;k++){
A[k]=binary(ters[S[k]], ters[E[k]],L[k], R[k]);
}
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();
std::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();
}
std::vector<int> A = check_validity(N, X, Y, S, E, L, R);
//for(int i=0;i<querys.size ();i++)cout<<querys[i]<<" "<<querys1[i]<<" "<<endl;
for (size_t i = 0; i < A.size(); ++i) {
printf("%d\n", A[i]);
}
return 0;
}*/
Compilation message
werewolf.cpp: In function 'void dfs(int)':
werewolf.cpp:29:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<G[x].size ();i++){
~^~~~~~~~~~~~~
werewolf.cpp: In function 'void dfs1(int, int)':
werewolf.cpp:66:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<G[x].size();i++){
~^~~~~~~~~~~~
werewolf.cpp: In function 'void dfs2(int, int)':
werewolf.cpp:74:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<G[x].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:107:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<X.size ();i++){
~^~~~~~~~~~
werewolf.cpp:122:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(sw1==1 and X.size ()+1==n){
~~~~~~~~~~~^~~
werewolf.cpp:172:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0;i<X.size();i++){
~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1617 ms |
39396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
