#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 10;
int n;
int in[MAXN];
vector<int> ar[MAXN];
vector<int> ord;
vector<int> id;
pair<int, int> seg[4 * MAXN];
void dfs(int cur, int pai){
ord.push_back(cur);
for(int i = 0; i < ar[cur].size(); i++){
int viz = ar[cur][i];
if(pai == viz) continue;
dfs(viz, cur);
}
}
void build(int pos, int ini, int fim){
if(ini == fim){
seg[pos] = make_pair(ord[ini], ord[ini]);
return;
}
int mid = (ini + fim) >> 1, e = pos << 1, d = e | 1;
build(e, ini, mid);
build(d, mid + 1, fim);
seg[pos].first = max(seg[e].first, seg[d].first);
seg[pos].second = min(seg[e].second, seg[d].second);
}
pair<int, int> query(int pos, int ini, int fim, int p, int q){
if(ini > q || fim < p) return make_pair(-1, n + 1);
if(ini >= p && fim <= q) return seg[pos];
int mid = (ini + fim) >> 1, e = pos << 1, d = e | 1;
pair<int, int> eVal = query(e, ini, mid, p, q);
pair<int, int> dVal = query(d, mid + 1, fim, p, q);
pair<int, int> ret;
ret.first = max(eVal.first, dVal.first);
ret.second = min(eVal.second, dVal.second);
return ret;
}
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;
for(int i = 0; i < X.size(); i++){
ar[X[i]].push_back(Y[i]);
ar[Y[i]].push_back(X[i]);
in[i]++;
}
if(X.size() != N - 1) return vector<int> (E.size());
for(int i = 0; i < n; i++){
if(in[i] != 1) continue;
ord.clear();
dfs(i, i);
}
id = vector<int> (n);
for(int i = 0; i < ord.size(); i++){
id[ord[i]] = i;
// printf("%d ", ord[i]);
}
// printf("\n");
vector<int> ans(E.size());
build(1, 0, n - 1);
for(int i = 0; i < E.size(); i++){
int a = id[S[i]];
int b = id[E[i]];
if(a < b){
int ini = a, fim = b;
while(ini != fim){
int mid = (ini + fim) >> 1;
if(ini == fim - 1) mid = fim;
pair<int, int> qVal = query(1, 0, n - 1, a, mid);
if(qVal.second >= L[i]) ini = mid;
else fim = mid - 1;
}
pair<int, int> qVal = query(1, 0, n - 1, ini, b);
ans[i] = qVal.first <= R[i];
}
else{
int ini = b, fim = a;
while(ini != fim){
int mid = (ini + fim) >> 1;
if(ini == fim - 1) mid = fim;
pair<int, int> qVal = query(1, 0, n - 1, b, mid);
if(qVal.first <= R[i]) ini = mid;
else fim = mid - 1;
}
pair<int, int> qVal = query(1, 0, n - 1, ini, a);
ans[i] = qVal.second >= L[i];
}
}
return ans;
}
Compilation message
werewolf.cpp: In function 'void dfs(int, int)':
werewolf.cpp:16:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
16 | for(int i = 0; i < ar[cur].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:49:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | for(int i = 0; i < X.size(); i++){
| ~~^~~~~~~~~~
werewolf.cpp:54:14: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
54 | if(X.size() != N - 1) return vector<int> (E.size());
| ~~~~~~~~~^~~~~~~~
werewolf.cpp:61:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | for(int i = 0; i < ord.size(); i++){
| ~~^~~~~~~~~~~~
werewolf.cpp:68:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | for(int i = 0; i < E.size(); i++){
| ~~^~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
4940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
4940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
4075 ms |
32636 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
4940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
