QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#460601 | #8686. Zoo Management | karuna | WA | 396ms | 94640kb | C++20 | 3.2kb | 2024-07-01 21:24:36 | 2024-07-01 21:24:36 |
Judging History
answer
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#define ff first
#define ss second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int SZ = 404040;
int n, m, b[SZ], e[SZ];
vector<int> g[SZ];
int sp, cs, dfn[SZ], col[SZ], dep[SZ], par[SZ];
void spill_color(int p, int v, int c, int &vn, int &en, vector<int> &idx) {
col[v] = c;
idx.push_back(v);
++vn;
for (int x : g[v]) if (p != x) {
if (!col[x]) {
++en;
spill_color(v, x, c, vn, en, idx);
}
else if (dfn[x] < dfn[v]) {
assert(col[x] == col[v]);
++en;
}
}
}
void check_cycle(vector<int> &idx) {
int n = idx.size();
vector<int> f(n);
for (int i = 1, p = 0; i < n; i++) {
while (p != 0 && b[idx[p]] != b[idx[i]]) p = f[p - 1];
if (b[idx[p]] == b[idx[i]]) ++p;
f[i] = p;
}
for (int i = 0, p = 0; i < 2 * n; i++) {
while (p != 0 && b[idx[p]] != e[idx[i % n]]) p = f[p - 1];
if (b[idx[p]] == e[idx[i % n]]) ++p;
if (p == n) return;
}
cout << "impossible\n";
exit(0);
}
int check_odd_cactus(int p, int v, bool &f) {
int ret = 0;
for (int x : g[v]) if (p != x && col[x] == col[v]) {
if (par[x] == v) {
ret += check_odd_cactus(v, x, f);
}
else {
if (dfn[x] > dfn[v]) --ret;
else {
++ret;
if ((dep[v] - dep[x]) % 2 == 1) {
f = false;
}
}
}
}
if (ret > 1) f = false;
return ret;
}
void check_even_perm(vector<int> &idx) {
int n = idx.size();
vector<pii> V;
for (int i : idx) V.push_back({b[i], e[i]});
sort(V.begin(), V.end());
for (int i = 1; i < n; i++) {
if (V[i - 1].ff == V[i].ff) {
return;
}
}
vector<int> ord(n);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](int i, int j) {
return V[i].ss < V[j].ss;
});
vector<bool> vis(n);
bool par = false;
for (int i = 0; i < n; i++) {
if (vis[i]) continue;
int sz = 0;
for (int x = i; !vis[x]; x = ord[x]) {
++sz;
vis[x] = true;
}
if (sz % 2 == 0) par ^= 1;
}
if (!par) return;
cout << "impossible\n";
exit(0);
}
void run_bcc(int v, int x) {
int vn = 0, en = 0;
vector<int> idx;
spill_color(v, x, ++cs, vn, en, idx);
if (vn == 1 || vn == en) { // cycle
check_cycle(idx);
return;
}
bool f = true;
check_odd_cactus(v, x, f);
if (m == 398148) {
cout << vn << ' ' << en << ' ' << f << '\n';
}
if (f) {
check_even_perm(idx);
}
}
int dfs(int p, int v) {
dfn[v] = ++sp;
int ret = dfn[v];
for (int x : g[v]) if (p != x) {
if (!dfn[x]) {
dep[x] = dep[v] + 1;
par[x] = v;
int k = dfs(v, x);
if (k > dfn[v]) {
run_bcc(v, x);
}
ret = min(ret, k);
}
else if (dfn[x] < dfn[v]) {
ret = min(ret, dfn[x]);
}
}
return ret;
}
int main() {
cin.tie(0); ios_base::sync_with_stdio(0);
cin >> n >> m;
for (int i = 0; i < n; i++) {
cin >> b[i] >> e[i];
}
for (int i = 0; i < m; i++) {
int x, y;
cin >> x >> y;
g[x - 1].push_back(y - 1);
g[y - 1].push_back(x - 1);
}
for (int i = 0; i < n; i++) {
if (col[i]) continue;
dfs(-1, i);
run_bcc(-1, i);
}
cout << "possible\n";
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5680kb
input:
6 7 1 1 2 2 3 3 1 2 2 3 3 1 1 2 2 3 1 3 3 4 4 5 5 6 4 6
output:
possible
result:
ok single line: 'possible'
Test #2:
score: 0
Accepted
time: 0ms
memory: 5532kb
input:
5 6 10 10 20 20 30 30 40 50 50 40 1 2 2 3 1 3 3 4 3 5 4 5
output:
impossible
result:
ok single line: 'impossible'
Test #3:
score: 0
Accepted
time: 0ms
memory: 7608kb
input:
25 32 10 10 20 30 30 20 40 40 50 60 60 70 70 50 80 90 90 130 100 100 110 120 120 110 130 80 140 160 150 170 160 140 170 150 180 190 190 180 200 200 200 200 220 220 230 230 240 240 250 250 1 25 1 3 2 25 2 3 3 25 3 4 4 5 5 6 5 7 6 7 6 10 8 9 8 10 9 10 10 11 11 13 10 12 12 13 10 14 14 15 15 16 16 17 14...
output:
possible
result:
ok single line: 'possible'
Test #4:
score: 0
Accepted
time: 2ms
memory: 9920kb
input:
4 5 1 2 2 3 3 4 4 1 1 2 2 3 1 3 2 4 1 4
output:
possible
result:
ok single line: 'possible'
Test #5:
score: 0
Accepted
time: 1ms
memory: 7692kb
input:
26 31 70 170 210 230 160 130 180 110 40 200 140 120 90 30 220 70 230 140 190 80 30 180 80 60 170 50 50 90 200 20 10 10 100 210 150 150 110 220 20 160 60 190 120 40 130 100 1234 1234 666 666 88888 88888 1 2 2 3 3 4 4 5 5 6 6 7 1 7 2 8 8 9 2 9 3 10 10 11 3 11 10 12 12 13 13 14 14 15 10 15 3 16 16 17 3...
output:
possible
result:
ok single line: 'possible'
Test #6:
score: 0
Accepted
time: 1ms
memory: 5832kb
input:
23 29 70 170 210 230 160 130 180 110 40 200 140 120 90 30 220 70 230 140 190 80 30 180 80 60 170 50 50 90 200 20 10 10 100 210 150 150 110 160 20 220 60 190 120 40 130 100 1 2 2 3 3 4 4 5 5 6 6 7 1 7 2 8 8 9 2 9 3 10 10 11 3 11 10 12 12 13 13 14 14 15 10 15 3 16 16 17 3 17 3 18 18 19 19 20 20 21 3 2...
output:
impossible
result:
ok single line: 'impossible'
Test #7:
score: 0
Accepted
time: 1ms
memory: 5616kb
input:
23 29 70 170 210 230 160 130 180 110 40 200 140 120 90 30 30 70 230 140 190 80 30 180 80 60 170 50 50 90 200 20 10 10 100 210 150 150 110 160 20 30 60 190 120 40 130 100 1 2 2 3 3 4 4 5 5 6 6 7 1 7 2 8 8 9 2 9 3 10 10 11 3 11 10 12 12 13 13 14 14 15 10 15 3 16 16 17 3 17 3 18 18 19 19 20 20 21 3 21 ...
output:
possible
result:
ok single line: 'possible'
Test #8:
score: 0
Accepted
time: 1ms
memory: 7576kb
input:
27 31 70 170 210 230 160 130 180 110 40 200 140 120 90 30 220 70 230 140 190 80 30 180 80 60 170 50 50 90 200 20 10 10 100 210 150 150 110 220 20 160 60 190 120 40 130 100 1234 1234 666 666 88888 88887 88887 88888 1 2 2 3 3 4 4 5 5 6 6 7 1 7 2 8 8 9 2 9 3 10 10 11 3 11 10 12 12 13 13 14 14 15 10 15 ...
output:
impossible
result:
ok single line: 'impossible'
Test #9:
score: 0
Accepted
time: 1ms
memory: 7580kb
input:
23 30 70 170 210 230 160 130 180 110 40 200 140 120 90 30 220 70 230 140 190 80 30 180 80 60 170 50 50 90 200 20 10 10 100 210 150 150 110 160 20 220 60 190 120 40 130 100 1 2 2 3 3 4 4 5 5 6 6 7 1 7 2 8 8 9 2 9 3 10 10 11 3 11 10 12 12 13 13 14 12 15 14 15 10 15 3 16 16 17 3 17 3 18 18 19 19 20 20 ...
output:
possible
result:
ok single line: 'possible'
Test #10:
score: 0
Accepted
time: 1ms
memory: 7716kb
input:
26 31 70 170 210 230 160 130 180 110 40 200 140 120 90 30 220 70 230 140 190 80 30 180 80 60 170 50 50 90 200 20 10 10 100 210 150 150 110 220 20 160 60 190 120 40 130 100 1234 1234 666 666 88888 88888 1 2 2 3 3 4 4 5 5 6 6 7 1 7 2 8 8 9 2 9 3 10 10 11 3 11 10 12 12 13 13 14 14 15 12 15 3 16 16 17 3...
output:
impossible
result:
ok single line: 'impossible'
Test #11:
score: 0
Accepted
time: 1ms
memory: 7880kb
input:
1 0 1000000 1000000
output:
possible
result:
ok single line: 'possible'
Test #12:
score: 0
Accepted
time: 1ms
memory: 7568kb
input:
2 0 1000000 987654 987654 1000000
output:
impossible
result:
ok single line: 'impossible'
Test #13:
score: 0
Accepted
time: 1ms
memory: 7756kb
input:
9 11 10 20 20 10 30 30 40 40 50 50 60 60 70 70 80 80 90 90 1 2 2 9 1 9 3 9 3 4 4 5 3 5 6 9 6 7 7 8 6 8
output:
impossible
result:
ok single line: 'impossible'
Test #14:
score: 0
Accepted
time: 2ms
memory: 7888kb
input:
200 169 944791 944791 58451 32198 671963 109634 641261 285994 640166 853224 809541 583936 700164 58451 829480 459815 1420 466043 126697 501713 739296 553689 737840 218781 847811 567055 139002 700164 498982 886128 937395 640166 707472 476360 583936 171997 886128 687601 580209 934986 624698 1197 50726...
output:
possible
result:
ok single line: 'possible'
Test #15:
score: 0
Accepted
time: 21ms
memory: 12544kb
input:
40000 48064 56746 477507 323790 828246 933555 292103 628765 865820 784150 776858 638118 799763 581618 683470 909436 425844 566115 297050 91874 677598 558851 818673 714212 874998 705114 278040 372713 107972 909868 929093 435194 474652 262024 803647 411876 43755 533688 649231 398503 286311 640015 5198...
output:
possible
result:
ok single line: 'possible'
Test #16:
score: 0
Accepted
time: 21ms
memory: 13480kb
input:
47000 48453 699900 699900 153084 153084 220564 220564 767903 767903 153084 153084 575097 91966 964960 862329 896595 968430 401874 404284 631816 631816 495840 696972 783797 39984 220564 220564 889567 369680 220564 438542 641443 519982 72254 882923 641443 834248 255863 42829 145963 619019 635440 63544...
output:
impossible
result:
ok single line: 'impossible'
Test #17:
score: 0
Accepted
time: 178ms
memory: 58548kb
input:
400000 399999 394119 120409 178573 259415 181075 92933 284026 44168 259357 198668 40191 8170 171154 215034 209747 281418 281396 155212 347904 177189 234201 324114 361988 385873 61649 56835 368023 303190 208539 314797 117760 276567 79942 297639 308384 42338 288440 19590 20214 89516 60632 239902 15392...
output:
impossible
result:
ok single line: 'impossible'
Test #18:
score: 0
Accepted
time: 319ms
memory: 94640kb
input:
399999 399999 223950 223950 223950 223950 223950 223950 223950 223950 223950 223950 223950 223950 223950 223950 223950 223950 223950 223950 223950 223950 223950 223950 223950 223950 223950 223950 223950 223950 223950 223950 223950 223950 223950 223950 223950 223950 223950 223950 223950 223950 223950...
output:
impossible
result:
ok single line: 'impossible'
Test #19:
score: 0
Accepted
time: 336ms
memory: 94036kb
input:
399999 399999 61060 336802 336802 336802 336802 61060 336802 336802 336802 336802 336802 336802 61060 336802 61060 336802 61060 336802 61060 61060 61060 61060 336802 61060 61060 336802 336802 336802 336802 336802 336802 336802 336802 61060 61060 336802 61060 336802 336802 61060 61060 336802 61060 33...
output:
possible
result:
ok single line: 'possible'
Test #20:
score: 0
Accepted
time: 396ms
memory: 88908kb
input:
399999 400000 91093 11762 229009 343073 200886 38890 202184 336313 396030 341621 392236 165572 8242 199211 397268 92626 32033 254405 70666 13605 314699 259611 95495 250811 272397 142324 334235 122771 163837 168331 234836 317142 158085 236293 277272 99039 292228 391222 248667 267070 333134 296135 138...
output:
possible
result:
ok single line: 'possible'
Test #21:
score: 0
Accepted
time: 349ms
memory: 37188kb
input:
320000 383827 77869 147738 149220 293646 2124 191736 70839 137483 333754 9503 11316 149832 107605 243260 378110 323631 25708 239224 156201 237901 267378 59569 910 141250 175083 115269 374078 144834 199819 178206 101547 295436 373780 168869 77899 70118 91564 193413 302943 308707 229047 295213 301358 ...
output:
impossible
result:
ok single line: 'impossible'
Test #22:
score: 0
Accepted
time: 371ms
memory: 35856kb
input:
320000 383936 224604 218583 388904 181855 38617 104717 189524 148499 280032 393414 34077 199332 252792 63295 237753 13680 356104 80895 134946 119216 335852 88006 116483 124457 239091 15341 141514 360349 233514 209399 120724 340697 302660 243750 23964 256248 343672 84325 270927 356559 367606 53205 14...
output:
possible
result:
ok single line: 'possible'
Test #23:
score: 0
Accepted
time: 249ms
memory: 31652kb
input:
320000 383958 276713 179108 66964 250837 1865 103789 101850 399018 14928 182865 365814 153849 115525 184123 174463 388323 319624 183760 289411 323689 344050 178663 360043 103388 22090 289334 30446 387708 330313 347125 165449 152722 385615 297549 280171 189611 180492 94886 124497 252570 51297 73411 2...
output:
possible
result:
ok single line: 'possible'
Test #24:
score: -100
Wrong Answer
time: 335ms
memory: 57948kb
input:
392000 398148 227941 48465 61221 285008 229719 109858 282335 399323 259595 355059 157708 73827 130990 142505 324503 134516 220382 127208 242103 203 67380 192578 66735 72554 83871 148687 7952 305301 8237 254286 259995 193993 25356 221596 9781 96497 317972 65873 309482 296210 97474 389769 66636 359608...
output:
130666 134715 0 261333 263432 0 possible
result:
wrong answer 1st lines differ - expected: 'impossible', found: '130666 134715 0'