#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[8*TAM+10];
int tree1[8*TAM+10];
int ters[8*TAM+10];
int aux[2][8*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 )
{
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:30:19: 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:80:19: 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:91:19: 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:214:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<X.size(); i++)
~^~~~~~~~~
werewolf.cpp:149:9: warning: unused variable 'sw1' [-Wunused-variable]
int sw1=0;/*
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1391 ms |
17836 KB |
Output is correct |
| 2 |
Correct |
1458 ms |
26272 KB |
Output is correct |
| 3 |
Correct |
1479 ms |
26360 KB |
Output is correct |
| 4 |
Correct |
1493 ms |
26268 KB |
Output is correct |
| 5 |
Correct |
1473 ms |
26360 KB |
Output is correct |
| 6 |
Correct |
1433 ms |
26260 KB |
Output is correct |
| 7 |
Correct |
1465 ms |
26232 KB |
Output is correct |
| 8 |
Correct |
1442 ms |
26264 KB |
Output is correct |
| 9 |
Correct |
725 ms |
26360 KB |
Output is correct |
| 10 |
Correct |
851 ms |
26320 KB |
Output is correct |
| 11 |
Correct |
966 ms |
26256 KB |
Output is correct |
| 12 |
Correct |
1030 ms |
26232 KB |
Output is correct |
| 13 |
Correct |
1470 ms |
26180 KB |
Output is correct |
| 14 |
Correct |
1633 ms |
26188 KB |
Output is correct |
| 15 |
Correct |
1471 ms |
26364 KB |
Output is correct |
| 16 |
Correct |
1484 ms |
26232 KB |
Output is correct |
| 17 |
Correct |
1437 ms |
26224 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
