#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
typedef long long ll;
const int N=200005;
int n,m,q;
vector<int> v[N];
vector<int> solve_small(vector<int> ns,vector<int> ne,vector<int> nl,vector<int> nr)
{
vector<int> res(q,0);
for(int o=0;o<q;o++)
{
int s=ns[o];
int e=ne[o];
int l=nl[o];
int r=nr[o];
vector<array<int,2>> dp(n,{0,0});
queue<array<int,2>> b;
auto add=[&](int a,int t)
{
if(dp[a][t]==0)
{
dp[a][t]=1;
b.push({a,t});
}
};
add(s,0);
while(!b.empty())
{
auto [a,t]=b.front();
b.pop();
if(l<=a&&a<=r&&t==0) add(a,1);
for(int to:v[a])
{
if(t==0&&to>=l) add(to,0);
if(t==1&&to<=r) add(to,1);
}
}
res[o]=dp[e][1];
}
return res;
}
vector<int> check_validity(int nn,vector<int> nx,vector<int> ny,vector<int> ns,vector<int> ne,vector<int> nl,vector<int> nr)
{
n=nn;
m=nx.size();
q=ns.size();
for(int i=0;i<m;i++)
{
v[nx[i]].push_back(ny[i]);
v[ny[i]].push_back(nx[i]);
}
if(n<=3000&&m<=6000&&q<=3000) return solve_small(ns,ne,nl,nr);
}
//int main()
//{
//
// return 0;
//}
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:58:1: warning: control reaches end of non-void function [-Wreturn-type]
58 | }
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
4940 KB |
Output is correct |
2 |
Correct |
5 ms |
4940 KB |
Output is correct |
3 |
Correct |
4 ms |
4996 KB |
Output is correct |
4 |
Correct |
5 ms |
4940 KB |
Output is correct |
5 |
Correct |
5 ms |
5004 KB |
Output is correct |
6 |
Correct |
5 ms |
4940 KB |
Output is correct |
7 |
Correct |
6 ms |
4996 KB |
Output is correct |
8 |
Correct |
5 ms |
4940 KB |
Output is correct |
9 |
Correct |
5 ms |
4940 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
4940 KB |
Output is correct |
2 |
Correct |
5 ms |
4940 KB |
Output is correct |
3 |
Correct |
4 ms |
4996 KB |
Output is correct |
4 |
Correct |
5 ms |
4940 KB |
Output is correct |
5 |
Correct |
5 ms |
5004 KB |
Output is correct |
6 |
Correct |
5 ms |
4940 KB |
Output is correct |
7 |
Correct |
6 ms |
4996 KB |
Output is correct |
8 |
Correct |
5 ms |
4940 KB |
Output is correct |
9 |
Correct |
5 ms |
4940 KB |
Output is correct |
10 |
Correct |
452 ms |
5420 KB |
Output is correct |
11 |
Correct |
306 ms |
5400 KB |
Output is correct |
12 |
Correct |
34 ms |
5400 KB |
Output is correct |
13 |
Correct |
386 ms |
5416 KB |
Output is correct |
14 |
Correct |
254 ms |
5396 KB |
Output is correct |
15 |
Correct |
303 ms |
5528 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
4046 ms |
26076 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
4940 KB |
Output is correct |
2 |
Correct |
5 ms |
4940 KB |
Output is correct |
3 |
Correct |
4 ms |
4996 KB |
Output is correct |
4 |
Correct |
5 ms |
4940 KB |
Output is correct |
5 |
Correct |
5 ms |
5004 KB |
Output is correct |
6 |
Correct |
5 ms |
4940 KB |
Output is correct |
7 |
Correct |
6 ms |
4996 KB |
Output is correct |
8 |
Correct |
5 ms |
4940 KB |
Output is correct |
9 |
Correct |
5 ms |
4940 KB |
Output is correct |
10 |
Correct |
452 ms |
5420 KB |
Output is correct |
11 |
Correct |
306 ms |
5400 KB |
Output is correct |
12 |
Correct |
34 ms |
5400 KB |
Output is correct |
13 |
Correct |
386 ms |
5416 KB |
Output is correct |
14 |
Correct |
254 ms |
5396 KB |
Output is correct |
15 |
Correct |
303 ms |
5528 KB |
Output is correct |
16 |
Execution timed out |
4046 ms |
26076 KB |
Time limit exceeded |
17 |
Halted |
0 ms |
0 KB |
- |