/*
Author of all code: Pedro BIGMAN Dias
Last edit: 15/02/2021
*/
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("Ofast")
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <list>
#include <iomanip>
#include <stdlib.h>
#include <time.h>
#include <cstring>
#include "werewolf.h"
using namespace std;
typedef int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"Pedro Is The Master "<<i<<endl
#define INF 10000000
#define EPS ((ld)0.00000000001)
#define pi ((ld)3.141592653589793)
#define VV(vvvv,NNNN,xxxx); REP(iiiii,0,NNNN) {vvvv.pb(xxxx);}
ll mod=1000000007LL;
template<class A=ll>
void Out(vector<A> a) {REP(i,0,a.size()) {cout<<a[i]<<" ";} cout<<endl;}
template<class A=ll>
void In(vector<A> &a, ll N) {A cur; REP(i,0,N) {cin>>cur; a.pb(cur);}}
class Graph
{
public:
ll N;
vector<vector<ll> > adj;
vector<bool> visited; //for DFS/BFS
vector<ll> current;
Graph() {ll N=0LL;}
Graph(vector<vector<ll> > ad)
{
adj=ad; N=adj.size(); REP(i,0,N) {visited.pb(false);}
}
void Reset()
{
REP(i,0,N) {visited[i]=false;}
}
void DFS(ll s)
{
if(visited[s]) {return;}
current.pb(s);
visited[s]=true;
REP(i,0,adj[s].size())
{
if(!visited[adj[s][i]]) {DFS(adj[s][i]);}
}
return;
}
};
template<class T=ll>
class SparseTable_min //Range Minimum Queries
{
public:
ll N;
vector<T> a;
vector<vector<T> > v;
SparseTable_min() {N=0LL;}
SparseTable_min(vector<T> b)
{
a=b; N=a.size();
ll lo=(ll) floor((ld) log2(N)) +1LL;
vector<T> xx;
REP(i,0,lo) {xx.pb(INF);} REP(i,0,N) {v.pb(xx);}
REP(step,0LL,lo)
{
REP(i,0,N-(1LL<<step)+1LL)
{
if(step==0) {v[i][0]=a[i];}
else {v[i][step]=min(v[i][step-1],v[i+(1LL<<(step-1))][step-1]);}
}
}
}
T query(ll l, ll r)
{
ll step=(ll) floor((ld) log2(r-l+1LL));
return min(v[l][step],v[r-(1LL<<step)+1LL][step]);
}
};
template<class T=ll>
class SparseTable_max //Range Minimum Queries
{
public:
ll N;
vector<T> a;
vector<vector<T> > v;
SparseTable_max() {N=0LL;}
SparseTable_max(vector<T> b)
{
a=b; N=a.size();
ll lo=(ll) floor((ld) log2(N)) +1LL;
vector<T> xx;
REP(i,0,lo) {xx.pb(0);} REP(i,0,N) {v.pb(xx);}
REP(step,0LL,lo)
{
REP(i,0,N-(1LL<<step)+1LL)
{
if(step==0) {v[i][0]=a[i];}
else {v[i][step]=max(v[i][step-1],v[i+(1LL<<(step-1))][step-1]);}
}
}
}
T query(ll l, ll r)
{
ll step=(ll) floor((ld) log2(r-l+1LL));
return max(v[l][step],v[r-(1LL<<step)+1LL][step]);
}
};
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R)
{
ll M = X.size();
vector<vector<ll> > adj; VV(adj,N,{});
REP(i,0,M) {adj[X[i]].pb(Y[i]); adj[Y[i]].pb(X[i]);}
Graph G(adj); ll s; REP(i,0,N) {if(adj[i].size()==1) {s=i; break;}}
G.DFS(s);
vector<ll> p = G.current;
unordered_map<ll,ll> m; REP(i,0,N) {m[p[i]]=i;}
ll Q = S.size();
vector<ll> ans;
SparseTable_max<ll> S_max(p); SparseTable_min<ll> S_min(p);
REP(i,0,Q)
{
ll A = m[S[i]]; ll B = m[E[i]];
ll C,D; ll lo,hi,mid;
if(A<=B)
{
//C is last after A prefix >= L[i]
//D is first before B suffix <= R[i]
lo=A,hi=B;
while(lo<hi)
{
mid=(lo+hi+1)/2;
if(S_min.query(A,mid)>=L[i]) {lo=mid;}
else {hi=mid-1;}
}
C=lo;
lo=A,hi=B;
while(lo<hi)
{
mid=(lo+hi)/2;
if(S_max.query(mid,B)<=R[i]) {hi=mid;}
else {lo=mid+1;}
}
D=lo;
if(C>=D) {ans.pb(1);} else {ans.pb(0);}
}
else
{
//C is first before A suffix >= L[i]
//D is last after B prefix <= R[i]
lo=B,hi=A;
while(lo<hi)
{
mid=(lo+hi+1)/2;
if(S_max.query(B,mid)<=R[i]) {lo=mid;}
else {hi=mid-1;}
}
D=lo;
lo=B,hi=A;
while(lo<hi)
{
mid=(lo+hi)/2;
if(S_min.query(mid,A)>=L[i]) {hi=mid;}
else {lo=mid+1;}
}
C=lo;
if(C<=D) {ans.pb(1);} else {ans.pb(0);}
}
}
return ans;
}
Compilation message
werewolf.cpp:5: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
5 | #pragma GCC optimization ("O3")
|
werewolf.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
6 | #pragma GCC optimization ("unroll-loops")
|
werewolf.cpp: In constructor 'Graph::Graph()':
werewolf.cpp:57:17: warning: unused variable 'N' [-Wunused-variable]
57 | Graph() {ll N=0LL;}
| ^
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:71:21: warning: 's' may be used uninitialized in this function [-Wmaybe-uninitialized]
71 | if(visited[s]) {return;}
| ^
werewolf.cpp:151:19: note: 's' was declared here
151 | Graph G(adj); ll s; REP(i,0,N) {if(adj[i].size()==1) {s=i; break;}}
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1099 ms |
91764 KB |
Output is correct |
| 2 |
Correct |
1097 ms |
92096 KB |
Output is correct |
| 3 |
Correct |
1105 ms |
100248 KB |
Output is correct |
| 4 |
Correct |
1152 ms |
100260 KB |
Output is correct |
| 5 |
Correct |
1120 ms |
100440 KB |
Output is correct |
| 6 |
Correct |
1161 ms |
100244 KB |
Output is correct |
| 7 |
Correct |
1077 ms |
100312 KB |
Output is correct |
| 8 |
Correct |
992 ms |
100456 KB |
Output is correct |
| 9 |
Correct |
466 ms |
100228 KB |
Output is correct |
| 10 |
Correct |
525 ms |
100232 KB |
Output is correct |
| 11 |
Correct |
574 ms |
100312 KB |
Output is correct |
| 12 |
Correct |
593 ms |
100264 KB |
Output is correct |
| 13 |
Correct |
1178 ms |
100484 KB |
Output is correct |
| 14 |
Correct |
1133 ms |
100364 KB |
Output is correct |
| 15 |
Correct |
1192 ms |
100308 KB |
Output is correct |
| 16 |
Correct |
1109 ms |
100252 KB |
Output is correct |
| 17 |
Correct |
1095 ms |
100216 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
