QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#874768#2744. WerewolfAlimkhan#0 1ms3840kbC++231.6kb2025-01-28 15:26:272025-01-28 15:26:27

Judging History

This is the latest submission verdict.

  • [2025-01-28 15:26:27]
  • Judged
  • Verdict: 0
  • Time: 1ms
  • Memory: 3840kb
  • [2025-01-28 15:26:27]
  • Submitted

answer

#include "werewolf.h"
#include <bits/stdc++.h>

using namespace std;

#define ff first
#define ss second

int dst[(int)2e5 + 10];
vector <pair <int, int> > g[(int)2e5 + 10];
deque <int> q;

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 Q = S.size();
  int n = N;
  int m = X.size();
  std::vector<int> A(Q);
  for (int k = 0; k < Q; ++k) {
	  for (int i = 0; i < n; i++) {
		  g[i].clear();
		  dst[i] = (int)1e9 + 7;
	  }
	  for (int i = 0; i < m; i++) {
		  if ((X[i] < L[k] && Y[i] > R[k]) || (X[i] > R[k] && Y[i] < L[k])) {
			  continue;
		  }
		  if (X[i] >= L[k] && X[i] <= R[k] && Y[i] < L[k]) {
			  g[X[i]].push_back({Y[i], 1});
			  g[Y[i]].push_back({X[i], 0});
			  continue;
		  }
		  if (Y[i] >= L[k] && Y[i] <= R[k] && X[i] < L[k]) {
			  g[X[i]].push_back({Y[i], 0});
			  g[Y[i]].push_back({X[i], 1});
			  continue;
		  }
		  g[X[i]].push_back({Y[i], 0});
		  g[Y[i]].push_back({X[i], 0});
	  }
	  q.push_back(S[k]);
	  dst[S[k]] = 0;
	  while(q.size() > 0) {
		  int v = q.front();
		  q.pop_front();
		  for (auto to: g[v]) {
			  if (dst[v] > 0 && to.ff > R[k]) continue;
			  if (dst[v] > 0 && to.ff < L[k]) continue;
			  if (dst[to.ff] > dst[v] + to.ss) {
				  dst[to.ff] = dst[v] + to.ss;
				  if (to.ss == 0) {
				  	q.push_front(to.ff);
				  } else {
					 q.push_back(to.ff);
				  }
			  }
		  }
	  }
	  if (dst[E[k]] != (int)1e9 + 7) {
		  A[k] = 1;
	  } else {
		  A[k] = 0;
	  }
  }
  return A;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3840kb

input:

100 200 100
11 23
5 9
2 88
19 18
78 90
90 52
25 30
52 71
35 43
39 29
62 17
69 49
26 82
84 83
38 87
70 19
73 57
1 97
39 95
86 70
99 82
73 17
62 96
69 53
92 91
58 42
43 34
16 76
83 35
45 94
0 52
75 14
6 35
42 5
25 60
32 44
91 63
33 46
80 68
87 30
84 32
24 25
18 56
40 11
17 12
2 18
88 28
96 42
38 70
8 ...

output:

1
1
1
0
1
1
1
1
0
0
1
1
1
0
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
0
1
1
1
1
0
1
0
0
1
0
1
1
1
1
1
1
1
1
1
1
1
0
1
1
0
1
1
1
1
0
0
0
1
1
1
1
1
1
1
1
0
1
1
1
1
0
1
0
1
1
1
1
1
1
1

result:

wrong answer 9th numbers differ - expected: '1', found: '0'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Time Limit Exceeded

Test #16:

score: 0
Time Limit Exceeded

input:

199998 199997 200000
156420 49950
49336 22370
148090 141451
185151 70518
45372 65839
2998 189479
99170 146949
110684 156207
28346 46533
193782 24138
46001 10975
12619 195136
88630 187635
23105 65382
119494 191355
70047 182323
47837 131580
63544 9529
73072 41503
141680 118088
3091 2117
138076 49422
6...

output:

Unauthorized output

result:


Subtask #4:

score: 0
Skipped

Dependency #1:

0%