QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#578564 | #9319. Bull Farm | WQhuanm | WA | 235ms | 37716kb | C++17 | 2.5kb | 2024-09-20 20:02:31 | 2024-09-20 20:02:32 |
Judging History
answer
// #pragma GCC optimize(2, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
#define endl "\n"
const int N = 2010, M = 1e6 + 5;
int n, m, Q;
int t[N][N], d[5], ok[N];
bool ans[M];
int fa[N];
vector<int> edge[N];
bitset<2001> bit[N];
int find(int x) {
if (fa[x] != x) fa[x] = find(fa[x]);
return fa[x];
}
void add(int x, int y) {
x = find(x), y = find(y);
if (x == y) return;
for (auto v : edge[y]) edge[x].push_back(v);
fa[y] = x, bit[x] |= bit[y];
for (auto v : edge[x]) bit[find(v)] |= bit[x];
}
void mysolve() {
cin >> n >> m >> Q;
string s;
for (int i = 1; i <= m; ++i) {
cin >> s, ok[i] = 0;
vector<int> tmp(n + 1);
for (int j = 0; j < (int)s.size(); j += 2) {
int a = s[j] - 48, b = s[j + 1] - 48, x = a * 50 + b;
t[i][(j >> 1) + 1] = x, tmp[x]++;
if (tmp[x] > 2) ok[i] = -1;
else if (tmp[x] == 2) {
if (!ok[i]) ok[i] = x;
else ok[i] = -1;
}
}
}
vector<array<int, 4>> ask;
for (int i = 1; i <= Q; ++i) {
cin >> s;
for (int i = 0; i < (int)s.size(); i += 2) {
int a = s[i] - 48, b = s[i + 1] - 48;
d[i >> 1] = a * 50 + b;
}
ask.push_back({d[2], d[0], d[1], i});
}
sort(ask.begin(), ask.end());
for (int i = 1; i <= n; ++i) bit[i].reset(), bit[i][i] = 1, fa[i] = i, edge[i].clear();
int j = 0;
for (int i = 1; i <= m; ++i) {
while (j < (int)ask.size() && ask[j][0] < i) {
auto [tim, a, b, id] = ask[j++];
ans[id] = bit[find(b)][a];
}
if (!ok[i]) {
for (int k = 1; k <= n; ++k) add(k, t[i][k]);
} else if (~ok[i]) {
vector<int> now;
for (int k = 1; k <= n; ++k)
if (t[i][k] == ok[i]) now.push_back(k);
assert((int)now.size() == 2);
set<int> mex;
for (int k = 1; k <= n; ++k) mex.insert(t[i][k]);
for (int k = 1; k <= n; ++k)
if (!mex.count(k)) {
for (auto v : now) bit[find(k)] |= bit[find(v)], edge[find(v)].push_back(find(k));
break;
}
}
}
while (j < (int)ask.size()) {
auto [tim, a, b, id] = ask[j++];
ans[id] = bit[find(b)][a];
}
for (int i = 1; i <= Q; ++i) cout << ans[i];
cout << endl;
}
signed main() {
#ifdef DEBUG
freopen("in.in", "r", stdin);
freopen("out.out", "w", stdout);
#endif
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); // 使用read请把解绑注释了
int t = 1;
cin >> t;
while (t--) {
mysolve();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5628kb
input:
2 5 2 4 0305040201 0404040404 030300 020500 050102 020501 6 2 4 030603010601 010203060504 030202 060402 050602 060401
output:
1011 0100
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 1ms
memory: 5732kb
input:
1 3 3 6 020202 030301 030201 020102 030203 010201 010303 020303 010202
output:
010101
result:
ok single line: '010101'
Test #3:
score: 0
Accepted
time: 163ms
memory: 3864kb
input:
200 10 10 5000 01060:04020305080709 0103070:060204050908 09070503080401060:02 050308010204090:0607 03010502040607080:09 03080109020504060:07 06050:09040302080107 07080305010409060:02 030809010:0204060507 0:060908070201050304 060700 090:03 09080: 070405 010703 0:0100 080601 030600 070206 0:0:09 08040...
output:
011110001101101111111111111111111101111111110111011110110110111011010111111111111111111101111111111110111111110111111111111101111111111110111111111111111111110001100111111111111111111111111011101111111111111111111111111111111111111111011011110100111110111111110111111100111111101110111111111101111110...
result:
ok 200 lines
Test #4:
score: 0
Accepted
time: 200ms
memory: 22632kb
input:
1 2000 1 1000000 M=:]A@8UAY7W2JJ4KEHIA[HSCQ1ENSC`JXR;F3PJ:_@41P9Z=9HR8P<<:DUXRR9^WOQFL?NZP6S@=J0^WE32=6;\U0?88]Q_RNPUMT6YU<4<S]H?:7OCQYOT4YAV1^764ENWSDBED>M7A:BI>KSIR48JQ9B=N\5T3N4A2aF0@>3TI81<G7;YE>W`NMP<:IT4CI3D0=GZC3I\CLQJQBA9BDIS9SAM55KaVA<Z@D=>:Y?CQHUQ5U3a6UVI8OKX9_FAF^7=5M85;<0;8YPAM<7Z7PP7A=N...
output:
000101000101100010001000000010010110000001000001001100000000010000100001000000101100000000010000001000000001110000010110100000111100100000001000000000011001010001000001001000100000000100011001100110010000010000101100000011111000000010000101010010000000010101000001010111100000100000000000000101000100...
result:
ok single line: '000101000101100010001000000010...0101000101000000000010101001000'
Test #5:
score: 0
Accepted
time: 204ms
memory: 37232kb
input:
1 2000 2000 1000000 FVAaH7GRPO;_11Da5J18@3SMG==\G8E8S^6:M4L0JH>MN5IXT>2<7WJ3U8LVJS=;;3F13>0D0>VOIIU@EPHG6ABL6;K?T1PXDERLG07]5C9^GDKG<SBMIW;`4W8P3=469TIPKH0O34523_J5C2MJ17D25Z@=K8H@M>WK<CMK7EO]BPD7B6AW741J5YIHIa1:ERSG>L3N2^F3<4F`DLE@2AA5=8GZK6:192FB736[WMV7:^DA2C:<LK040VJBM3M]WXU50`407TR_?PLF@5VL7OSL...
output:
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
result:
ok single line: '111111111111111111111111111111...1111111111111111111111111111111'
Test #6:
score: 0
Accepted
time: 235ms
memory: 37716kb
input:
1 2000 2000 1000000 0102030405060708090:0;0<0=0>0?0@0A0B0C0D0E0F0G0H0I0J0K0L0M0N0O0P0Q0R0S0T0U0V0W0X0Y0Z0[0\0]0^0_0`0a101112131415161718191:1;1<1=1>1?1@1A1B1C1D1E1F1G1H1I1J1K1L1M1N1O1P1Q1R1S1T1U1V1W1X1Y1Z1[1\1]1^1_1`1a202122232425262728292:2;2<2=2>2?2@2A2B2C2D2E2F2G2H2I2J2K2L2M2N2O2P2Q2R2S2T2U2V2W2X...
output:
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000...
result:
ok single line: '000000000000000000000000000000...0000000000000000000000000000000'
Test #7:
score: 0
Accepted
time: 219ms
memory: 36528kb
input:
1 2000 2000 1000000 0102030405060708090:0;0<0=0>0?0@0A0B0C0D0E0F0G0H0I0J0K0L0M0N0O0P0Q0R0S0T0U0V0W0X0Y0Z0[0\0]0^0_0`0a101112131415161718191:1;1<1=1>1?1@1A1B1C1D1E1F1G1H1I1J1K1L1M1N1O1P1Q1R1S1T1U1V1W1X1Y1Z1[1\1]1^1_1`1a202122232425262728292:2;2<2=2>2?2@2A2B2C2D2E2F2G2H2I2J2K2L2M2N2O2P2Q2R2S2T2U2V2W2X...
output:
010001100010000000101000000110010001001010101100100100000001000000101010100010000001011111010000000001001000010101011111001010101010100100010001011011000010010100110110000100010110101110000011111101100110010100100101010000100100101110100000000101100010100111000011001110100010001010000101111001101000...
result:
ok single line: '010001100010000000101000000110...1010101000010010101000100000111'
Test #8:
score: 0
Accepted
time: 208ms
memory: 36640kb
input:
1 2000 2000 1000000 0102030405060708090:0;0<0=0>0?0@0A0B0C0D0E0F0G0H0I0J0K0L0M0N0O0P0Q0R0S0T0U0V0W0X0Y0Z0[0\0]0^0_0`0a101112131415161718191:1;1<1=1>1?1@1A1B1C1D1E1F1G1H1I1J1K1L1M1N1O1P1Q1R1S1T1U1V1W1X1Y1Z1[1\1]1^1_1`1a202122232425262728292:2;2<2=2>2?2@2A2B2C2D2E2F2G2H2I2J2K2L2M2N2O2P2Q2R2S2T2U2V2W2X...
output:
011010100000000000000000001000001100000110000000100001010000000000000010001000000100000000000000000000100000100000000001100000100011010000000000000000000000000010000001000000010001100010000100000001000000000010000000000000001000010100000000001000000000000000000000001100010000000000000101000000101010...
result:
ok single line: '011010100000000000000000001000...0000000000000100000010010000100'
Test #9:
score: 0
Accepted
time: 233ms
memory: 36460kb
input:
1 2000 2000 1000000 1REKN]@]>9D9177?6E8DU65LCS>X3Z4KJ47@?R43H8C2ADQ<T[GGCZI]CO4SCDNAVCE534S1;0LV<:F[R`A[=89FL^BYGU7F:NBDD2F3SYLQS[O407E\V>>;EOTL=W8VAYMRO[KHRZ7^F6?:<G4R9O3AVG1\1OER1MKNMG01R?=;SWMP28:X>2=GLC1LSU<VMKQ5?KQAS^4QDTC07TK=R01WL@6596@D5IKT?YG?HaQPP:<12ZUF?GARFKJXC`NFIaJ;SXC:80V1Q@Q;FJV]3XSJ...
output:
111101100101100100000000101000110011010001100000001001101000001000010101010010100111100010100110000001000000011101001010110000101000111000010011110100010101100101011111000010000001100001000011010001101000000010100011000110101001100010111010110011001101110010001110110101000000110111010100001000011001...
result:
ok single line: '111101100101100100000000101000...1100010101000011110011110111100'
Test #10:
score: 0
Accepted
time: 170ms
memory: 36288kb
input:
1 1 2000 1000000 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 0...
output:
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
result:
ok single line: '111111111111111111111111111111...1111111111111111111111111111111'
Test #11:
score: 0
Accepted
time: 203ms
memory: 37236kb
input:
1 2000 2000 1000000 1ILZ2@SO4;BPWLFN@6HMAVQ]NNKR2NU30EP@3WF73^1BSKIP:VS7KQA>T\T63TAAK]8a4@7F0LD3V4LRN?M105L@>A<5D@S=MI9G9O<7<UQaF61VK;EQBEG`F8DOJ?L67;CL=@Q_IAPU2TP:43=O42I85UC\2L18KKP5MSFX73;\PFCQ:IB9?M<:FI?;N1I1>362O:;:1WQ6=Q7T=RW\WJMTQJ40U6JU>_@H:H6K0Y?[>H@K6@5AG]OEUEH>3G5C@OJ1E8O0CaO68??>A\C`:F8T...
output:
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
result:
ok single line: '111111111111111111111111111111...1111111111111111111111111111111'
Test #12:
score: 0
Accepted
time: 201ms
memory: 37256kb
input:
1 2000 2000 1000000 =H=4F4S`A?@V<E8]HBU>190VP7EDDC6EH3P4CP6K2Z3OP@LI<7H`OM:F:=FOH9BW=<1ZGIK^7P0<9RK73Z1EFKO5QC5L25TCV`HT3D@RQ_2GE<SK;_D^0;>FSL5X9_Q0L\L7TW@_ULQE0Z;MG1O:3>F<MX=:V];@=1A@;^V^E\;F:[8S@SFY340R=@Wa8NSMS[UC5KV6JNV3EA<80_;a>`2:>A28OI=EL2?aTDL3WRNY4H8R2aIY14DAHJ>6UIEOS_?=AF6];\BK3]?<TYU5=`3^...
output:
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
result:
ok single line: '111111111111111111111111111111...1111111111111111111111111111111'
Test #13:
score: 0
Accepted
time: 166ms
memory: 6008kb
input:
200 10 10 5000 08060705040203010:09 0201090:080706050304 0201050903080:060407 0305010:020706090804 030901080:0706040205 0509070:010803060204 0:060709080203050401 0309010806050:040207 020106090703050:0408 0603020908010:050407 020700 080907 020305 070407 050509 080502 010100 020206 050809 0:0807 02040...
output:
011111111111111111101111111111111111111111111111101011111011111110111010111111111111110111111111111111111011101111111111111010110011011111111111111111011001110110101111110100111101111101101111011111111111111111111110011111110011111110111111101111111110111100111111111111111111111111111111111101011111...
result:
ok 200 lines
Test #14:
score: -100
Wrong Answer
time: 157ms
memory: 3752kb
input:
400 5 5 2500 0405020501 0404050302 0105050105 0304010205 0402030205 040200 010203 040203 030503 050201 010502 010505 030304 020504 050503 050105 030101 020403 030403 030200 010500 050500 030403 050101 040205 030501 010503 050400 030505 040303 050101 020101 050502 020104 050101 040503 010205 050404 0...
output:
000000010100000010010000100110000010010000100000100110011000100110101000010000010010010111000000011000001000000010000011010000000110000110010100101011010010110100011000000010011010110000100110111000000101001010010100010000111101011010111101001100000011100001000000000000111000000001100010001100010000...
result:
wrong answer 5th lines differ - expected: '100011011001011100100000100110...1000000100110001000100010011010', found: '100011011001011100100000100110...1000000100110001000100010011010'