QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #874778 | #2744. Werewolf | Alimkhan# | 15 | 271ms | 6420kb | C++23 | 1.7kb | 2025-01-28 15:52:04 | 2025-01-28 15:52:04 |
Judging History
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.clear();
q.push_back(S[k]);
dst[S[k]] = 0;
while(q.size() > 0) {
int v = q.front();
q.pop_front();
// cout << v << '\n';
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) {
// cout << dst[E[k]] << '\n';
A[k] = 1;
} else {
A[k] = 0;
}
}
return A;
}
詳細信息
Subtask #1:
score: 7
Accepted
Test #1:
score: 7
Accepted
time: 1ms
memory: 5972kb
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 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 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 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
result:
ok 100 numbers
Test #2:
score: 7
Accepted
time: 0ms
memory: 3840kb
input:
100 99 100 69 88 29 91 33 24 11 40 49 11 1 5 73 11 99 19 71 82 28 55 44 14 85 99 67 96 39 89 31 29 39 20 53 72 97 49 24 23 81 37 45 27 58 81 44 76 66 85 15 68 1 12 27 8 28 48 33 61 55 56 84 68 62 91 44 7 74 65 3 86 78 60 79 7 35 72 0 52 21 26 4 44 34 76 56 43 78 32 13 45 75 47 92 30 18 2 1 89 75 26 ...
output:
1 1 1 0 0 0 1 1 1 1 1 1 1 0 1 1 1 1 0 1 0 1 1 0 1 1 1 0 0 1 1 0 1 0 0 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 0 1 1 1 0 0 0 1 0 0 0 1 0 0 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 0 1 0 1 0 1 1 0 1 1 1 1 1 0 1 1
result:
ok 100 numbers
Test #3:
score: 7
Accepted
time: 2ms
memory: 3840kb
input:
21 200 100 18 1 0 9 17 8 4 9 15 14 0 15 2 8 15 20 14 1 3 6 7 1 5 13 12 3 5 1 2 7 3 19 4 20 12 8 12 15 0 14 7 15 20 16 11 1 11 8 11 5 14 8 15 1 11 4 18 17 13 18 10 0 14 19 19 2 16 8 15 18 15 17 9 14 11 20 9 20 9 15 9 17 11 0 4 12 17 11 16 6 20 1 20 12 8 5 13 9 18 9 19 16 13 2 18 11 7 12 18 14 7 19 8 ...
output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
result:
ok 100 numbers
Test #4:
score: 7
Accepted
time: 0ms
memory: 3840kb
input:
7 8 100 0 5 5 6 2 5 1 5 1 4 5 3 3 1 0 1 1 4 1 5 2 0 1 5 4 2 1 6 5 2 2 4 3 6 2 6 0 6 0 6 0 4 0 4 3 4 2 6 1 6 0 6 0 1 0 5 2 5 2 5 6 2 2 2 0 6 0 6 2 1 2 6 4 0 1 4 3 4 3 5 2 6 1 6 1 0 0 4 4 1 4 5 6 2 2 2 2 5 2 6 2 6 1 6 1 5 1 6 4 0 1 3 6 3 2 3 0 5 0 6 5 3 3 3 2 3 2 5 4 5 0 6 1 4 1 5 2 6 0 6 2 4 0 4 0 5 ...
output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
result:
ok 100 numbers
Test #5:
score: 7
Accepted
time: 0ms
memory: 5964kb
input:
100 110 100 78 34 93 78 85 11 12 65 55 96 92 88 80 91 58 38 44 85 15 46 9 55 84 70 47 65 82 71 37 25 81 71 23 2 57 35 75 8 14 47 85 53 40 82 99 25 22 97 39 79 45 62 69 59 48 62 56 32 60 19 17 55 31 5 52 23 7 59 56 64 96 87 35 84 45 94 31 18 61 64 30 72 21 59 96 85 96 68 91 41 82 53 7 65 4 24 51 99 1...
output:
0 1 1 1 1 1 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 0 1 0 0 0 1 1 1 1 1 1 1 1 1 1 0 1 1 0 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 0 1 0 1 1 1 1 1 1 0
result:
ok 100 numbers
Test #6:
score: 7
Accepted
time: 1ms
memory: 5968kb
input:
100 130 100 72 65 15 55 40 30 11 74 92 10 52 17 12 30 92 14 31 43 35 54 20 14 16 10 17 89 50 24 75 95 7 89 10 3 80 33 11 8 81 59 63 49 17 51 57 29 53 77 76 28 85 31 28 3 83 38 66 40 21 4 10 60 71 62 68 12 56 6 75 89 80 10 37 23 92 97 9 44 9 27 33 23 0 77 8 24 35 61 1 21 7 70 57 85 72 54 15 66 92 80 ...
output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 0 1 1 1 0 1 0 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 1 1 1 1 0 1 1 1 1 1
result:
ok 100 numbers
Test #7:
score: 7
Accepted
time: 1ms
memory: 5972kb
input:
100 120 100 22 87 67 95 63 62 90 0 68 75 24 83 16 72 61 1 31 68 2 41 92 85 13 34 41 33 29 3 30 78 35 9 8 34 71 36 93 59 67 17 74 99 44 40 55 12 80 86 43 37 2 48 11 32 82 3 21 25 25 12 30 92 77 43 44 32 72 70 0 69 95 31 55 52 58 56 45 47 8 3 85 54 70 71 49 76 33 99 15 38 49 29 66 7 38 40 55 27 65 4 9...
output:
0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 0 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 0 0 1 1 1 1 0 1 1 1 1 0 1 1 0 0 1 1 1 1 1 1 1 1 0 1 1 1
result:
ok 100 numbers
Test #8:
score: 7
Accepted
time: 0ms
memory: 3840kb
input:
100 99 100 28 9 88 21 60 81 5 15 75 1 57 63 11 41 11 25 68 37 63 39 38 39 61 78 91 74 10 98 32 10 7 95 4 22 49 56 45 30 4 88 59 33 20 51 2 25 27 86 59 40 76 78 23 58 99 66 14 80 3 89 72 12 47 18 65 49 71 98 62 90 51 83 8 93 70 44 35 67 13 97 46 40 21 38 16 52 23 37 66 96 26 8 64 77 48 41 0 89 96 26 ...
output:
1 1 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 1 1 0 0 0 1 1 0 1 1 0 0 1 1 0 0 1 0 0 0 1 1 1 0 0 1 0 0 0
result:
ok 100 numbers
Test #9:
score: 7
Accepted
time: 0ms
memory: 3840kb
input:
100 110 100 41 61 0 6 13 70 24 82 31 87 43 63 0 3 38 10 92 23 84 73 17 1 37 99 89 30 19 80 69 3 4 8 9 49 93 18 24 10 21 36 38 44 0 1 94 57 77 98 18 96 29 11 7 1 5 78 66 36 16 21 79 67 22 39 3 10 40 54 19 37 28 5 12 67 13 16 13 19 46 9 30 29 8 26 7 59 91 59 4 48 2 50 67 73 14 56 13 1 9 90 15 7 51 16 ...
output:
1 1 1 1 1 1 1 0 1 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 0 1 1 1
result:
ok 100 numbers
Subtask #2:
score: 8
Accepted
Dependency #1:
100%
Accepted
Test #10:
score: 8
Accepted
time: 256ms
memory: 6252kb
input:
3000 3300 3000 155 1238 2134 2071 979 2819 1920 2593 2493 2966 967 639 2107 2424 981 1846 738 873 2613 1769 2697 118 2865 2855 1676 1939 205 1721 11 1745 2862 2248 1110 518 1038 2390 792 1879 2549 396 641 975 1676 695 1485 577 1048 2682 1398 2832 1754 1571 642 2288 1436 2835 2534 2318 581 1978 2860 ...
output:
1 1 1 1 1 1 1 0 1 1 0 1 1 1 1 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 0 0 0 1 1 ...
result:
ok 3000 numbers
Test #11:
score: 8
Accepted
time: 186ms
memory: 4096kb
input:
3000 2999 3000 430 272 49 929 1648 1738 1366 2195 620 1833 382 1795 2349 2092 1376 396 1080 2896 2515 2988 1784 2847 419 2760 2815 646 206 2052 915 2928 1799 1541 1222 2030 2419 1245 941 1388 1197 1931 1455 45 1484 1115 847 1368 985 64 540 2220 1871 606 1101 673 2457 2896 1051 123 2967 1920 1682 170...
output:
1 0 1 0 1 1 1 0 1 0 0 1 0 1 0 0 1 1 1 0 0 1 1 1 1 1 1 1 1 1 0 0 0 1 0 0 0 1 1 0 1 0 0 1 0 1 1 0 0 1 0 1 1 0 1 0 1 1 0 1 0 1 0 1 1 1 1 1 1 1 1 0 0 1 0 1 0 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 0 0 1 1 1 0 0 1 0 1 1 1 1 0 1 1 1 0 0 1 0 1 0 1 0 1 1 0 1 0 1 1 0 1 0 1 1 0 1 0 1 1 1 0 0 0 0 0 1 0 0 1 1 1 1 1 1 ...
result:
ok 3000 numbers
Test #12:
score: 8
Accepted
time: 100ms
memory: 6116kb
input:
3000 2999 3000 689 1178 1290 846 344 267 2963 1661 328 1804 2387 2913 349 232 384 337 2030 2643 2851 2242 188 1078 573 1185 1048 1711 1786 2418 410 1898 1124 2282 1419 2195 516 1963 83 2979 2191 2341 488 335 2644 547 1045 2034 2496 1244 627 2955 864 795 560 1560 816 2615 519 378 645 2707 1696 1364 2...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 3000 numbers
Test #13:
score: 8
Accepted
time: 271ms
memory: 6208kb
input:
3000 3300 3000 1918 305 1536 675 1997 764 263 2124 32 1776 698 71 1113 788 101 86 2007 2795 1153 2572 464 632 2268 2133 1267 842 1113 1723 41 210 1063 2733 907 1960 1350 1426 1731 1895 560 495 220 471 102 515 1305 1355 726 634 670 1343 1796 2678 1276 1187 2038 1677 1112 433 1467 2320 67 53 252 788 2...
output:
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 1 0 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 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 0 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 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 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
ok 3000 numbers
Test #14:
score: 8
Accepted
time: 206ms
memory: 6244kb
input:
3000 2999 3000 1753 2871 112 569 1259 394 1550 2748 1615 1031 382 830 713 1435 605 267 384 1437 633 1111 1223 26 506 320 586 131 702 2189 27 79 821 1877 2588 2937 2420 2062 2040 1476 1551 1538 1967 616 457 2481 436 2001 298 807 2264 1465 435 1101 1864 1579 862 1331 342 5 1495 1749 674 1471 1228 1214...
output:
1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 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 0 ...
result:
ok 3000 numbers
Test #15:
score: 8
Accepted
time: 201ms
memory: 6420kb
input:
3000 6000 3000 1399 725 1595 179 1728 387 1775 1135 2679 2493 1207 356 850 1324 2349 1588 2257 1713 754 2056 2651 2437 1890 2866 997 2631 552 2994 1182 490 22 2046 814 192 1862 2472 2320 917 2807 1327 1240 2450 309 1797 2638 2127 312 352 552 1674 1950 1746 1488 1402 1018 463 1106 2808 2432 2756 2533...
output:
0 0 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 ...
result:
ok 3000 numbers
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:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
0%