#include "bits/stdc++.h"
#include "werewolf.h"
using namespace std;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
vector<vector<int>> adj;
vector<int> em;
vector<int> path;
vector<pair<int, int>> sorted_path;
void bfs(int n, int S, int E)
{
vector<bool> visited(n, false);
vector<int> parent(n, -1);
queue<int> q;
q.push(S);
bool flag = true;
visited[S] = true;
while(!q.empty()&&flag)
{
int u = q.front();
q.pop();
visited[u] = true;
for(auto v: adj[u])
{
if(visited[v])
continue;
parent[v] = u;
q.push(v);
if(v==E)
flag = false;
}
}
vector<int> p;
int x = E;
while(x!=-1)
{
p.pb(x);
x = parent[x];
}
reverse(p.begin(), p.end());
path = p;
}
int bs(int x)
{
int l = 0, r = (int)sorted_path.size();
while(l<=r)
{
int mid = l + (r-l)/2;
if(sorted_path[mid].fi==x)
return sorted_path[mid].se;
if(sorted_path[mid].fi<x)
l = mid+1;
else
r = mid-1;
}
return -1;
}
const int Q = 200000;
vector<int> check_validity(int n, vector<int> x, vector<int> y, vector<int> s, vector<int> e, vector<int> l, vector<int> r)
{
int m = (int)x.size();
int q = (int)l.size();
vector<int> res(q, 0);
adj.assign(n, em);
pair<int, int> boundary = mp(-1, -1);
for(int i = 0; i<m; i++)
{
adj[x[i]].pb(y[i]);
adj[y[i]].pb(x[i]);
}
for(int i = 0; i<n; i++)
{
if((int)adj[i].size()==1)
{
if(boundary.fi==-1)
boundary.fi = i;
else
{
boundary.se = i;
break;
}
}
}
bfs(n, boundary.fi , boundary.se);
int len = int(path.size());
for(int i = 0; i<len; i++)
{
sorted_path.pb(mp(path[i], i));
}
sort(sorted_path.begin(), sorted_path.end());
for(int querie = 0; querie<q; querie++)
{
int S = s[querie];
int E = e[querie];
int L = l[querie];
int R = r[querie];
bool flag = false;
bool reversed = false;
int ind_start = bs(S);
int ind_end = bs(E);
if(ind_end<ind_start)
reversed = true;
if(reversed)
{
int i = ind_start;
int last = ind_start;
while(i>ind_end)
{
if(path[i]>=L&&path[i]<=R)
last = i;
if(path[i]<L)
break;
i--;
}
if(i==ind_end)
flag = true;
else
{
i = last -1;
while(i>ind_end)
{
if(path[i]>R)
break;
i--;
}
if(i==ind_end)
flag = true;
}
}
else
{
int i = ind_start;
int last = ind_start;
while(i<ind_end)
{
if(path[i]>=L&&path[i]<=R)
last = i;
if(path[i]<L)
break;
i++;
}
i = last + 1;
while(i<ind_end)
{
if(path[i]>R)
break;
i++;
}
if(i==ind_end)
flag = true;
}
if(flag)
res[querie] = 1;
else
res[querie] = 0;
}
return res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
427 ms |
28044 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
