QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #291907 | #5704. Joker | whdywjd | 25 | 24ms | 16156kb | C++14 | 4.3kb | 2023-12-27 13:03:43 | 2023-12-27 13:03:44 |
Judging History
answer
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <set>
#define ll long long
#define _1 first
#define _2 second
#define _mp make_pair
#define _pb push_back
#define MAX_M 522222
using namespace std;
ll read(){ll x = 0;char c = 0, v = 0;do{c = getchar();if(c == '-')v = 1;} while(c < '0' || c > '9');do{x = (x << 3) + (x << 1) + c - '0';c = getchar();} while(c >= '0' && c <= '9');return v ? -x : x;}
template<size_t N>
struct vset
{
struct node
{
int id;
int x, y;
int fx, fy;
bool dx, dy;
} clr[N];
int tot;
int f[N];
bool d[N];
vset() { memset(f, 255, sizeof(f)), memset(d, 0, sizeof(d)); }
int fath(int x) { return f[x] < 0 ? x : fath(f[x]); }
bool col(int x)
{
bool cl = 0;
for(int i = x; i >= 0; i = f[i])
cl ^= d[i];
return cl;
}
bool check(int x, int y) { return fath(x) != fath(y) || col(x) != col(y); }
void merge(int x, int y, int id)
{
//return;
//printf("%d %d %d\n", x, y, id);
bool cx = col(x), cy = col(y);
x = fath(x), y = fath(y);
//return;
clr[++tot] = (node){id, x, y, f[x], f[y], d[x], d[y]};
//return;
if(x == y)
return;
if(f[x] > f[y])
swap(x, y);
if(cx == cy)
d[y] ^= 1;
f[x] += f[y];
f[y] = x;
}
inline int topid() { return clr[tot].id; }
void del()
{
int x = clr[tot].x, y = clr[tot].y;
f[x] = clr[tot].fx, f[y] = clr[tot].fy;
d[x] = clr[tot].dx, d[y] = clr[tot].dy;
tot--;
}
};
vset<MAX_M> st;
struct node { int u, v; };
int n, m, q;
node a[MAX_M];
int ans[MAX_M];
void dfs(int ql, int qr, int l, int r)
{
//printf("%d %d %d %d\n", ql, qr, l, r);
if(l == r)
{
for(int i = ql; i <= qr; i++)
ans[i] = l;
return;
}
int mid = (l + r) >> 1;
for(int i = r; i >= mid; i--)
{
if(!st.check(a[i].u, a[i].v))
{
while(st.topid() <= r && st.topid() >= mid)
st.del();
dfs(ql, qr, mid + 1, r);
while(st.topid() >= ql && st.topid() <= r)
st.del();
return;
}
st.merge(a[i].u, a[i].v, i);
}
//return;
for(int i = ql; i <= qr; i++)
{
//return;
if(!st.check(a[i].u, a[i].v))
{
//return;
while(st.topid() <= r && st.topid() >= mid)
st.del();
dfs(i, qr, mid + 1, r);
while(st.topid() < i && st.topid() >= ql)
st.del();
for(int j = r; j > mid; j--)
st.merge(a[j].u, a[j].v, j);
dfs(ql, i - 1, l, mid);
while(st.topid() >= ql && st.topid() <= r)
st.del();
return;
}
st.merge(a[i].u, a[i].v, i);
}
while(st.topid() >= ql && st.topid() <= r)
st.del();
for(int j = r; j > mid; j--)
st.merge(a[j].u, a[j].v, j);
dfs(ql, qr, l, mid);
while(st.topid() >= ql && st.topid() <= r)
st.del();
}
void MAIN()
{
n = read();
m = read();
q = read();
for(int i = 1; i <= m; i++)
a[i].u = read(), a[i].v = read();
for(int i = 0; i <= m; i++)
ans[i] = m + 2;
int lb = 0;
for(int i = 1; i <= m; i++)
{
if(!st.check(a[i].u, a[i].v))
break;
st.merge(a[i].u, a[i].v, i);
lb = i;
}
while(st.tot)
st.del();
dfs(1, lb, 1, m + 1);
ans[0] = m + 1;
for(int i = m; i; i--)
{
if(!st.check(a[i].u, a[i].v))
break;
st.merge(a[i].u, a[i].v, i);
ans[0] = i;
}
while(st.tot)
st.del();
/*for(int i = 1; i <= m; i++)
printf("%d ", ans[i]);
printf("\n");*/
for(int i = 1; i <= q; i++)
{
int l = read() - 1;
int r = read() + 1;
if(r >= ans[l])
printf("NO\n");
else
printf("YES\n");
}
}
void CLEAR()
{
;
}
void EXP()
{
;
}
int main()
{
EXP();
int T = 1;
while(T--)
MAIN(), CLEAR();
return 0;
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 6
Accepted
time: 0ms
memory: 9832kb
input:
6 8 2 1 3 1 5 1 6 2 5 2 6 3 4 3 5 5 6 4 8 4 7
output:
NO YES
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 1ms
memory: 8796kb
input:
2 1 1 1 2 1 1
output:
NO
result:
ok single line: 'NO'
Test #3:
score: 0
Accepted
time: 1ms
memory: 8396kb
input:
4 6 6 4 3 1 4 1 3 2 1 3 2 2 4 3 3 6 6 4 5 3 4 1 2 5 6
output:
YES YES YES YES YES YES
result:
ok 6 lines
Test #4:
score: -6
Wrong Answer
time: 0ms
memory: 8972kb
input:
3 3 6 1 2 2 3 3 1 1 1 1 2 1 3 2 2 2 3 3 3
output:
NO NO NO YES NO NO
result:
wrong answer 4th lines differ - expected: 'NO', found: 'YES'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 25
Accepted
Test #55:
score: 25
Accepted
time: 15ms
memory: 13760kb
input:
100000 199997 200000 79109 44896 79109 66117 66117 91800 91800 24387 24387 74514 48558 74514 48558 37561 37561 76920 79598 76920 79598 69196 69196 79004 49065 79004 70038 49065 15497 70038 15497 67507 25073 67507 25073 41762 41762 71848 71848 32073 32073 43754 72852 43754 41209 72852 68112 41209 629...
output:
NO NO YES NO NO NO NO NO NO NO NO NO NO YES NO YES NO NO NO NO NO YES NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO YES NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO YES NO NO YES NO NO YES NO NO NO YES NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO YES NO NO NO NO YES ...
result:
ok 200000 lines
Test #56:
score: 0
Accepted
time: 15ms
memory: 15544kb
input:
200000 200000 200000 156700 169748 169748 15408 158166 15408 117779 158166 2384 169748 4408 156700 117779 33510 90442 4408 4408 162134 117779 171528 90442 38746 33510 152759 171528 184558 162134 8761 154354 171528 23832 171528 23832 68341 98972 152759 80275 98972 98972 67486 67486 31710 31710 127052...
output:
NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO ...
result:
ok 200000 lines
Test #57:
score: 0
Accepted
time: 19ms
memory: 15540kb
input:
180000 200000 200000 95819 27342 123468 27342 95819 45980 95819 36699 71942 45980 36699 30023 30023 98714 30023 101707 71942 134121 148555 45980 45980 66377 74540 101707 66170 101707 67584 123468 66360 27342 95819 53123 101707 65852 148860 123468 148555 119737 143349 30023 148555 86262 66377 102544 ...
output:
NO NO NO NO YES YES NO NO NO NO NO YES NO YES YES NO NO NO YES NO YES NO NO NO NO NO NO NO NO NO YES NO YES NO NO NO NO NO YES NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO YES NO NO YES NO YES NO NO YES NO YES NO NO YES YES YES YES NO NO NO NO NO YES...
result:
ok 200000 lines
Test #58:
score: 0
Accepted
time: 20ms
memory: 11048kb
input:
100000 199998 200000 87308 6340 6340 65354 52754 87308 88178 52754 6340 5495 22090 52754 98806 22090 5495 73821 9604 52754 37077 52754 68317 37077 21343 68317 12967 98806 69585 68317 69585 28583 21343 69734 69585 20913 57662 69734 94110 91458 14376 69734 41402 57662 94921 14376 96594 58350 14376 578...
output:
NO NO YES NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO YES YES NO NO NO NO YES YES NO NO NO YES NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO YES NO YES YES NO YES NO NO YES YE...
result:
ok 200000 lines
Test #59:
score: 0
Accepted
time: 18ms
memory: 14116kb
input:
100000 199998 200000 28343 15804 28343 94432 28343 23326 59830 23326 10127 59830 28343 43794 10127 23571 23571 3145 43794 81307 3717 43794 66710 59830 21890 28343 28353 28343 3145 70155 28343 35892 70678 15804 10127 83329 3717 35392 73105 23571 3145 19619 87075 27586 90214 83329 32670 21890 22856 87...
output:
YES NO NO NO NO YES NO NO NO NO YES YES NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO YES NO NO NO NO NO NO YES NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO N...
result:
ok 200000 lines
Test #60:
score: 0
Accepted
time: 24ms
memory: 13920kb
input:
60000 200000 200000 47535 59290 4275 37708 43568 37576 957 18676 27619 37179 19026 4602 52742 32392 14534 22002 26055 47146 45919 41903 37887 56149 36060 42697 8741 313 28057 15816 56765 34869 26554 14156 12833 13682 44772 28577 18097 31289 36656 3501 40514 15833 26141 35850 19093 50872 40660 37526 ...
output:
YES NO YES YES YES YES YES YES YES YES NO YES YES NO YES NO YES NO YES YES YES YES YES YES NO NO NO YES YES NO YES YES YES NO YES YES YES YES YES YES YES YES NO YES YES YES YES NO YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES NO YES YES YES YES YES YES YES YES YES YES NO YE...
result:
ok 200000 lines
Test #61:
score: 0
Accepted
time: 19ms
memory: 16156kb
input:
100000 200000 200000 77786 6752 26401 60048 31910 17910 65779 52734 11872 54867 11498 82141 93189 80000 87783 60280 22166 77429 51584 95507 2261 30821 12929 59760 42423 48187 10729 26779 24258 74392 67495 60621 42163 26061 12641 11404 71465 82245 52055 3427 13752 34140 20925 31926 14287 97161 58584 ...
output:
YES YES YES NO YES YES NO YES YES YES YES YES NO YES YES YES YES YES YES YES NO YES NO YES YES YES YES YES YES NO YES YES YES YES YES YES NO YES YES YES YES YES YES YES NO NO YES NO YES NO YES YES YES YES YES YES YES YES YES YES YES YES NO YES YES YES YES YES YES NO YES NO YES NO YES YES NO YES YES ...
result:
ok 200000 lines
Test #62:
score: 0
Accepted
time: 24ms
memory: 14104kb
input:
200000 200000 200000 197731 68719 145501 57647 34483 149695 62098 31160 160935 43346 70944 126156 194438 93717 133681 33810 143842 4779 84849 63629 179978 147132 75441 104532 11976 28821 20385 110393 133541 21240 149042 64811 135285 3108 138414 165849 100523 121508 79580 92189 49291 44875 138988 711...
output:
NO YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES NO YES NO YES YES YES NO NO YES YES NO NO YES YES YES YES NO YES NO YES YES YES YES YES NO YES YES NO YES YES YES YES YES YES YES YES YES NO YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES NO YES NO YES YE...
result:
ok 200000 lines
Test #63:
score: 0
Accepted
time: 22ms
memory: 14084kb
input:
100000 200000 200000 91199 7467 35612 91199 7467 3610 7467 7468 3610 44904 44904 7468 91027 47259 44904 2753 48718 11316 11316 92818 23795 93555 93555 11316 5417 14329 93555 50009 90447 50009 93555 78407 14329 90447 73524 90447 21658 90447 56875 61966 21658 61966 19145 78407 56875 19145 79811 9701 6...
output:
NO NO NO NO NO NO NO NO NO NO YES NO YES NO NO NO NO NO NO NO YES YES NO NO NO NO NO NO NO NO NO NO NO YES YES NO YES NO YES NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO N...
result:
ok 200000 lines
Test #64:
score: 0
Accepted
time: 23ms
memory: 14132kb
input:
180000 200000 200000 48044 116141 149941 97532 108024 153885 48044 164680 167561 108024 164680 125849 81699 125849 125849 19101 117501 127237 70827 19101 14065 127237 127237 81126 93655 70827 41364 134339 125630 41364 125415 123173 142478 125630 2139 125415 50880 10270 142478 50880 136482 5039 14247...
output:
NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO YES NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO YES YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO YES NO YES NO NO NO NO NO YES NO NO YES YES YES NO NO NO NO NO NO NO NO NO NO YES NO NO N...
result:
ok 200000 lines
Test #65:
score: 0
Accepted
time: 16ms
memory: 11208kb
input:
20000 200000 200000 17080 3271 6065 5381 7484 15940 18311 3140 11602 9470 2894 1072 8425 4218 16737 8744 8615 12148 18845 15437 8863 4501 433 14607 835 12426 7833 1411 7614 13860 7554 16289 13415 12180 13972 15293 1191 15245 931 17175 19824 6768 10000 18782 12041 15601 7510 9734 17454 5230 16237 484...
output:
NO NO NO YES YES NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO YES NO NO YES NO YES NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO YES NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO YES NO NO YES NO YE...
result:
ok 200000 lines
Test #66:
score: 0
Accepted
time: 20ms
memory: 12888kb
input:
60000 200000 200000 47535 59290 4275 37708 43568 37576 957 18676 27619 37179 19026 4602 52742 32392 14534 22002 26055 47146 45919 41903 37887 56149 36060 42697 8741 313 28057 15816 56765 34869 26554 14156 12833 13682 44772 28577 18097 31289 36656 3501 40514 15833 26141 35850 19093 50872 40660 37526 ...
output:
NO NO NO NO NO NO YES NO NO NO NO NO NO NO YES NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO YES YES NO YES NO NO NO NO NO NO NO NO NO YES NO YES NO YES NO NO NO NO NO YES NO NO NO NO NO YES YES NO NO NO N...
result:
ok 200000 lines
Test #67:
score: 0
Accepted
time: 13ms
memory: 14112kb
input:
140000 200000 200000 76834 9131 135811 73947 77276 137710 49994 104785 76787 107620 17804 71946 123058 134210 18830 127913 46949 93779 38771 75648 69206 134597 16321 66343 65538 134280 37783 74563 82646 564 44569 137484 105009 10351 71026 49636 6687 22732 122561 92211 117741 6102 18948 37956 24674 1...
output:
NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO YES YES NO NO NO NO NO NO YES NO NO NO NO NO YES NO NO YES NO NO NO NO NO YES YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO...
result:
ok 200000 lines
Test #68:
score: 0
Accepted
time: 15ms
memory: 13492kb
input:
200000 200000 200000 197731 68719 145501 57647 34483 149695 62098 31160 160935 43346 70944 126156 194438 93717 133681 33810 143842 4779 84849 63629 179978 147132 75441 104532 11976 28821 20385 110393 133541 21240 149042 64811 135285 3108 138414 165849 100523 121508 79580 92189 49291 44875 138988 711...
output:
NO NO NO NO NO YES NO NO YES NO NO YES NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO YES NO YES NO NO NO YES NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO YES NO NO NO NO NO NO NO YES NO NO NO NO ...
result:
ok 200000 lines
Subtask #4:
score: 0
Wrong Answer
Dependency #3:
100%
Accepted
Test #69:
score: 0
Wrong Answer
time: 18ms
memory: 13764kb
input:
100000 199997 200000 1304 38053 86107 1304 68527 86107 68527 1612 66259 1612 66259 45383 45383 86918 86918 92171 8178 92171 8178 84276 84276 63841 68544 63841 68544 18174 3108 18174 15718 3108 79171 15718 79171 63115 2935 63115 19505 2935 69846 19505 79230 69846 79230 85213 43038 85213 43038 73657 7...
output:
YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES ...
result:
wrong answer 5th lines differ - expected: 'NO', found: 'YES'
Subtask #5:
score: 0
Skipped
Dependency #2:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%