//#pragma GCC target("avx2")
//#pragma GCC optimization("O3")
//#pragma GCC optimization("unroll-loops")
// #include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define pb push_back
#define SZ(x) ((int)(x).size())
#define all(x) x.begin(), x.end()
#define debug(x) cout << #x << ": " << x << " "
#define nl cout << "\n"
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
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 = SZ(X), Q = SZ(S);
if(M <= 10000 && Q <= 10000){
vector<int> g[N];
rep(i, 0, M){
int u = X[i], v = Y[i];
g[u].pb(v); g[v].pb(u);
}
vector<int> ans(Q);
rep(i, 0, Q){
int s = S[i], t = E[i], l = L[i], r = R[i];
int v = s;
queue<pii> q;
vector<vector<bool>> vis(2, vector<bool>(N, false));
q.push({s, 0}); vis[0][v] = true;
while(!q.empty()){
auto [v, k] = q.front();
q.pop();
if(k == 1 && v == t) break;
if(l <= v && v <= r && !vis[1][v]){
vis[1][v] = true;
q.push({v, 1});
}
for(int u : g[v]){
if(!k && u >= l){
if(!vis[k][u]){
vis[k][u] = true; q.push({u, k});
}
} else if(k && u <= r){
if(!vis[k][u]){
vis[k][u] = true; q.push({u, k});
}
}
}
}
ans[i] = (vis[1][t] == true);
}
return ans;
}
if(M == N - 1){
vector<int> g[N];
rep(i, 0, M){
int u = X[i], v = Y[i];
g[u].pb(v); g[v].pb(u);
}
vector<int> a, p(N);
rep(v, 0, N){
if(SZ(g[v]) == 1){
a.pb(v);
p[a.back()] = SZ(a) - 1;
while(SZ(a) < N){
v = a.back();
for(int u : g[v]){
if(SZ(a) == 1 || u != a[SZ(a) - 2]){
a.pb(u); p[a.back()] = SZ(a) - 1;
break;
}
}
}
break;
}
}
const int MAXK = 20;
int mnl[MAXK][N], mnr[MAXK][N], mxl[MAXK][N], mxr[MAXK][N];
rep(i, 0, N){
if(i > 0){
mnl[0][i] = min(a[i - 1], a[i]);
mxl[0][i] = max(a[i - 1], a[i]);
}
if(i < N - 1){
mnr[0][i] = min(a[i], a[i + 1]);
mxr[0][i] = max(a[i], a[i + 1]);
}
}
rep(k, 0, MAXK - 1){
rep(i, 0, N){
if(i + (1 << (k + 1)) < N){
mnr[k + 1][i] = min(mnr[k][i], mnr[k][i + (1 << k)]);
mxr[k + 1][i] = max(mxr[k][i], mxr[k][i + (1 << k)]);
}
if(i - (1 << (k + 1)) >= 0){
mnl[k + 1][i] = min(mnl[k][i], mnl[k][i - (1 << k)]);
mxl[k + 1][i] = max(mxl[k][i], mxl[k][i - (1 << k)]);
}
}
}
vector<int> ans(Q);
rep(i, 0, Q){
int s = S[i], t = E[i], l = L[i], r = R[i];
int ls = p[s], rs = p[s], lt = p[t], rt = p[t];
per(k, MAXK - 1, 0){
if(ls - (1 << k) >= 0 && mnl[k][ls] >= l){
ls -= (1 << k);
}
if(rs + (1 << k) < N && mnr[k][rs] >= l){
rs += (1 << k);
}
if(lt - (1 << k) >= 0 && mxl[k][lt] <= r){
lt -= (1 << k);
}
if(rt + (1 << k) < N && mxr[k][rt] <= r){
rt += (1 << k);
}
}
if(min(rs, rt) >= max(ls, lt)){
ans[i] = 1;
} else{
ans[i] = 0;
}
}
return ans;
}
}
Compilation message
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:37:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
37 | auto [v, k] = q.front();
| ^
werewolf.cpp:133:1: warning: control reaches end of non-void function [-Wreturn-type]
133 | }
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
245 ms |
876 KB |
Output is correct |
11 |
Correct |
175 ms |
876 KB |
Output is correct |
12 |
Correct |
16 ms |
748 KB |
Output is correct |
13 |
Correct |
196 ms |
820 KB |
Output is correct |
14 |
Correct |
136 ms |
876 KB |
Output is correct |
15 |
Correct |
251 ms |
876 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
787 ms |
76624 KB |
Output is correct |
2 |
Correct |
700 ms |
84192 KB |
Output is correct |
3 |
Correct |
671 ms |
84160 KB |
Output is correct |
4 |
Correct |
703 ms |
84192 KB |
Output is correct |
5 |
Correct |
704 ms |
84064 KB |
Output is correct |
6 |
Correct |
781 ms |
84064 KB |
Output is correct |
7 |
Correct |
629 ms |
84064 KB |
Output is correct |
8 |
Correct |
616 ms |
84088 KB |
Output is correct |
9 |
Correct |
531 ms |
84160 KB |
Output is correct |
10 |
Correct |
406 ms |
84184 KB |
Output is correct |
11 |
Correct |
430 ms |
84064 KB |
Output is correct |
12 |
Correct |
437 ms |
84064 KB |
Output is correct |
13 |
Correct |
698 ms |
84064 KB |
Output is correct |
14 |
Correct |
732 ms |
84064 KB |
Output is correct |
15 |
Correct |
717 ms |
84160 KB |
Output is correct |
16 |
Correct |
701 ms |
84160 KB |
Output is correct |
17 |
Correct |
634 ms |
84064 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
245 ms |
876 KB |
Output is correct |
11 |
Correct |
175 ms |
876 KB |
Output is correct |
12 |
Correct |
16 ms |
748 KB |
Output is correct |
13 |
Correct |
196 ms |
820 KB |
Output is correct |
14 |
Correct |
136 ms |
876 KB |
Output is correct |
15 |
Correct |
251 ms |
876 KB |
Output is correct |
16 |
Correct |
787 ms |
76624 KB |
Output is correct |
17 |
Correct |
700 ms |
84192 KB |
Output is correct |
18 |
Correct |
671 ms |
84160 KB |
Output is correct |
19 |
Correct |
703 ms |
84192 KB |
Output is correct |
20 |
Correct |
704 ms |
84064 KB |
Output is correct |
21 |
Correct |
781 ms |
84064 KB |
Output is correct |
22 |
Correct |
629 ms |
84064 KB |
Output is correct |
23 |
Correct |
616 ms |
84088 KB |
Output is correct |
24 |
Correct |
531 ms |
84160 KB |
Output is correct |
25 |
Correct |
406 ms |
84184 KB |
Output is correct |
26 |
Correct |
430 ms |
84064 KB |
Output is correct |
27 |
Correct |
437 ms |
84064 KB |
Output is correct |
28 |
Correct |
698 ms |
84064 KB |
Output is correct |
29 |
Correct |
732 ms |
84064 KB |
Output is correct |
30 |
Correct |
717 ms |
84160 KB |
Output is correct |
31 |
Correct |
701 ms |
84160 KB |
Output is correct |
32 |
Correct |
634 ms |
84064 KB |
Output is correct |
33 |
Execution timed out |
4048 ms |
30060 KB |
Time limit exceeded |
34 |
Halted |
0 ms |
0 KB |
- |