#include <bits/stdc++.h>
#include "werewolf.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define db long double
#define ii pair<int,int>
#define vi vector<int>
#define fi first
#define se second
#define sz(a) (int)(a).size()
#define all(a) (a).begin(),(a).end()
#define pb push_back
#define mp make_pair
#define FN(i, n) for (int i = 0; i < (int)(n); ++i)
#define FEN(i,n) for (int i = 1;i <= (int)(n); ++i)
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repv(i,a,b) for(int i=b-1;i>=a;i--)
#define SET(A, val) memset(A, val, sizeof(A))
typedef tree<int ,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set ;
// order_of_key (val): returns the no. of values less than val
// find_by_order (k): returns the kth largest element.(0-based)
#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ','); cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif
const int N=200005;
vi v[N];
bool vis[N];
void dfs(int u,int l,int r,vi &tmp,int type=0)
{
if(type==0 && u<l) return;
if(type==1 && u>r) return;
vis[u]=true;
tmp.pb(u);
for(int v1:v[u])
{
if(vis[v1]) continue;
dfs(v1,l,r,tmp,type);
}
}
vi subtask12(int n,vi S,vi E,vi L,vi R)
{
int q=sz(S);
vi ans(q,0);
rep(i,0,q)
{
int x=S[i],y=E[i],l=L[i],r=R[i];
if(x<l || y>r)
continue;
vi tmp1,tmp2;
rep(j,0,n) vis[j]=false;
dfs(x,l,r,tmp1);
dfs(y,l,r,tmp2,1);
sort(all(tmp1)); sort(all(tmp2));
bool ok=false;
for(int x:tmp1)
{
int ind=lower_bound(all(tmp2),x)-tmp2.begin();
if(ind!=sz(tmp2) && tmp2[ind]==x) ok=true;
}
if(ok) ans[i]=1;
}
return ans;
}
vi check_validity(int n,vi X,vi Y,vi S,vi E,vi L,vi R)
{
int q=sz(S);
rep(i,0,sz(X))
{
v[X[i]].pb(Y[i]);
v[Y[i]].pb(X[i]);
}
if(n<=3000 && q<=3000)
return subtask12(n,S,E,L,R);
return S;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
5112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
5112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
275 ms |
20812 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
5112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
