#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
/*
dati due nodi di inizio e fine,
sicuramente ci sarà un path o più path
che li collegano, noi stiamo cercando un path in particolare
colui che è decrescente
TUTTO CIO NON E UN ALBERO
*
posso modificare BFS + subtask3 con ST e fare 49 punti.
*/
vector<vector<int>> graph;
vector<int> V;
vector<int> MN, MX;
bool solver(int start, int end, int L, int R, int N){
vector<vector<bool>> visited(N, vector<bool>(2, 0));
queue<pair<int, bool>> q;
q.push({start, 1});
if(start >= L && start <= R) q.push({start, 0});
while(!q.empty()){
pair<int, bool> curr = q.front();
q.pop();
int node = curr.first;
bool human = curr.second;
vector<int> adj = graph[node];
visited[node][human] = true;
// cout<<"DEBUG-->"<<start<<" "<<node<<" "<<human<<endl;
for(int a : adj){
if(human){
// cout<<"DEBUG-->"<<start<<" "<<a<<" "<<L<<endl;
if(a < L) continue;
if(a >= L && a <= R && !visited[a][0]){
q.push({a, 0});
visited[a][0] = true;
}
if(visited[a][1]) continue;
q.push({a, 1});
visited[a][1] = true;
}else{
if(a > R) continue;
if(visited[a][0]) continue;
q.push({a, 0});
visited[a][0] = true;
}
}
}
if(visited[end][1] && end >= L && end <= R) return 1;
return visited[end][0];
}
/*
6 5 3
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
9 8 4
4 3
3 5
5 0
0 2
2 1
1 6
6 7
7 8
2 0 1 2
4 2 2 2
5 4 3 4
0 7 3 4
*
*/
void build(int p, int L, int R){
if(L == R){
MN[p] = V[L];
MX[p] = V[L];
return;
}
int mid = (L+R)/2;
build(p*2, L, mid);
build(p*2+1, mid+1, R);
MN[p] = min(MN[p*2], MN[p*2+1]);
MX[p] = max(MX[p*2], MX[p*2+1]);
}
int getMin(int p, int L, int R, int i, int j){
if(i > R || j < L) return INT_MAX;
if(i <= L && R <= j) return MN[p];
int mid = (L+R)/2;
return min(getMin(p*2, L, mid, i, j),getMin(p*2+1, mid+1, R, i, j));
}
int getMax(int p, int L, int R, int i, int j){
if(i > R || j < L) return -1;
if(i <= L && R <= j) return MX[p];
int mid = (L+R)/2;
return max(getMax(p*2, L, mid, i, j),getMax(p*2+1, mid+1, R, i, j));
}
std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
std::vector<int> S, std::vector<int> E,
std::vector<int> L, std::vector<int> R) {
int M = X.size();
int Q = L.size();
vector<int> ans(Q);
graph.assign(N, vector<int>());
MN.assign(N*4+1, 0);
MX.assign(N*4+1, 0);
for(int i = 0; i < M; i++){
graph[X[i]].push_back(Y[i]);
graph[Y[i]].push_back(X[i]);
}
bool subtask3 = M == N-1;
map<int, int> mp;
for(int i = 0; i < N; i++)
mp[graph[i].size()]++;
subtask3 = mp[1] == 2 && mp[2] == N-2;
if(subtask3){
// costruisco la catena
int root = 0;
for(int i = 0; i < N; i++) if(graph[i].size() == 1){root = i; break;}
int curr = root;
int prev = -1;
vector<bool> visited(N, 0);
while(curr != prev){
visited[curr] = true;
V.push_back(curr);
int next = curr;
for(int a : graph[curr]){
if(visited[a]) continue;
next = a;
}
prev = curr;
curr = next;
}
// for(int x = 0; x < N; x++) cout<<V[x]<<" ";
// cout<<endl;
build(1, 0, N-1);
map<int, int> mp;
for(int x = 0; x < N; x++)
mp[V[x]] = x;
for(int i = 0; i < Q; i++){
int idxS = mp[S[i]];
int idxE = mp[E[i]];
bool inv = idxS > idxE;
if(idxS > idxE) swap(idxS, idxE); // da sistemare
int low = idxS;
int high = idxE;
// cout<<"DEBUG-->"<<low<<" "<<high<<endl;
for(int i = 0; i < N; i++) cout<<V[i]<<" ";
cout<<endl;
while(low < high){
int mid = low + (high-low)/2;
if(!inv){
int mnLeft = getMin(1, 0, N-1, idxS, mid), mxRight = getMax(1, 0, N-1, mid+1, idxE);
if(mnLeft >= L[i] && mxRight <= R[i]){
// apposto NO!
if(V[mid] >= L[i] && V[mid] <= R[i]){
ans[i] = 1;
break;
}
if(V[mid] < L[i]){
low = mid+1;
}else if(V[mid] > R[i]) high = mid;
}else if(mnLeft < L[i]){
high = mid;
}else if(mxRight > R[i]){
low = mid+1;
}
}else{
int mxLeft = getMax(1, 0, N-1, idxS, mid), mnRight = getMin(1, 0, N-1, mid+1, idxE);
if(mnRight >= L[i] && mxLeft <= R[i]){
if(V[mid] >= L[i] && V[mid] <= R[i]){
ans[i] = 1;
break;
}
if(V[mid] < L[i]){
high = mid;
}else if(V[mid] > R[i]) low = mid+1;
}else if(mnRight < L[i]){
low = mid+1;
}else if(mxLeft > R[i]){
high = mid;
}
}
}
}
return ans;
}
for(int i = 0; i < Q; i++){
// adesso abbiamo L[i] ed R[i]
ans[i] = solver(S[i], E[i], L[i], R[i], N);
}
return ans;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
212 KB |
Output is correct |
| 2 |
Correct |
2 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
2 ms |
212 KB |
Output is correct |
| 6 |
Correct |
2 ms |
216 KB |
Output is correct |
| 7 |
Correct |
2 ms |
312 KB |
Output is correct |
| 8 |
Incorrect |
2 ms |
344 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
212 KB |
Output is correct |
| 2 |
Correct |
2 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
2 ms |
212 KB |
Output is correct |
| 6 |
Correct |
2 ms |
216 KB |
Output is correct |
| 7 |
Correct |
2 ms |
312 KB |
Output is correct |
| 8 |
Incorrect |
2 ms |
344 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
4043 ms |
313932 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
212 KB |
Output is correct |
| 2 |
Correct |
2 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
2 ms |
212 KB |
Output is correct |
| 6 |
Correct |
2 ms |
216 KB |
Output is correct |
| 7 |
Correct |
2 ms |
312 KB |
Output is correct |
| 8 |
Incorrect |
2 ms |
344 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
