QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#569265 | #9319. Bull Farm | duoluoluo | WA | 396ms | 40352kb | C++20 | 4.3kb | 2024-09-16 21:35:06 | 2024-09-16 21:35:06 |
Judging History
answer
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
#include <vector>
#include <queue>
#include <bitset>
using namespace std;
const int N = 2010;
int n, m, q, t[N][N], ans[1000010], num[N], fa[N];
int dfn[N], low[N], sta[N], vis[N], cnt, top;
bitset<N> b[N];
vector < vector < int > > colVec;
map<int, bool> e[N];
char s[N << 1];
struct Q {
int a, b, c, id;
} que[1000010];
bool cmp (Q a, Q b) {
return a.c < b.c;
}
int get (int x) {
return x == fa[x] ? x : fa[x] = get(fa[x]);
}
void dfs (int x) {
if (vis[x]) return;
vis[x] = 1;
for (auto y : e[x]) {
dfs(y.first);
b[x] |= b[y.first];
}
}
void tupo () {
for (int i = 1; i <= n; i ++) {
b[i].none();
b[i][i] = 1;
vis[i] = 0;
}
for (int i = 1; i <= n; i ++) {
if (get(i) == i && !vis[i])
dfs(i);
}
}
void tarjan (int x) {
dfn[x] = ++ cnt;
low[x] = cnt;
sta[++ top] = x;
vis[x] = 1;
for (auto [y, bl] : e[x]) {
if (!dfn[y]) {
tarjan(y);
low[x] = min(low[x], low[y]);
} else if (vis[y]) {
low[x] = min(low[x], low[y]);
}
}
if (dfn[x] == low[x]) {
vector < int > vec;
vis[x] = 0;
vec.emplace_back(x);
while (sta[top] != x) {
int y = sta[top--];
vis[y] = 0;
vec.emplace_back(y);
}
top--;
colVec.emplace_back(vec);
}
}
void addedge (int x, int y) {
if (x == y) return;
e[x][y] = 1;
}
void addbutton (int id) {
cnt = top = 0;
colVec.clear();
for (int i = 1; i <= n; i ++) num[i] = dfn[i] = low[i] = sta[i] = vis[i] = 0;
int flag = 0;
for (int i = 1; i <= n; i ++) {
num[t[id][i]] ++;
if (num[t[id][i]] > 2) return;
if (num[t[id][i]] == 2) {
if (flag) return;
flag = t[id][i];
}
}
if (flag) {
int d = 0;
for (int i = 1; i <= n; i ++)
if (!num[i])
d = i;
for (int i = 1; i <= n; i ++)
if (t[id][i] == flag) addedge(get(i), get(d));
} else {
for (int i = 1; i <= n; i ++)
addedge(get(i), get(t[id][i]));
}
for (int i = 1; i <= n; ++i) {
if (!dfn[i])
tarjan(i);
}
for (auto vec : colVec) {
int id = vec[0];
for (int x : vec) {
if (e[x].size() > e[id].size())
id = x;
}
for (int x : vec) {
if (x == id) continue;
for (auto [y, bl] : e[x]) {
e[id][y] = 1;
fa[x] = id;
}
}
}
for (int i = 1; i <= n; ++i) {
if (get(i) != i)
e[i].clear();
else {
vector < int > vec;
for (auto [y, bl] : e[i]) {
if (y == get(y))
vec.emplace_back(y);
}
e[i].clear();
for (int x : vec)
e[i][x] = 1;
}
}
}
void init () {
scanf("%d%d%d", &n, &m, &q);
for (int i = 1; i <= n; i ++) {
fa[i] = i;
e[i].clear();
}
for (int i = 1; i <= m; i ++) {
scanf("%s", s + 1);
for (int j = 1; j <= n; j ++)
t[i][j] = (s[(j * 2) - 1] - 48) * 50 + (s[(j * 2)] - 48);
}
for (int i = 1; i <= q; i ++) {
scanf("%s", s + 1);
que[i].a = (s[1] - 48) * 50 + (s[2] - 48);
que[i].b = (s[3] - 48) * 50 + (s[4] - 48);
que[i].c = (s[5] - 48) * 50 + (s[6] - 48);
que[i].id = i;
}
sort(que + 1, que + q + 1, cmp);
int qtop = 0;
for (int i = 1; i <= q; i ++) {
while (qtop < que[i].c) {
qtop ++;
addbutton(qtop);
}
tupo();
int j = i;
while (j <= q) {
if (b[get(que[j].a)][get(que[j].b)]) ans[que[j].id] = 1;
else ans[que[j].id] = 0;
if (que[j + 1].c != que[j].c) break;
j ++;
}
i = j;
}
for (int i = 1; i <= q; i ++) printf("%d", ans[i]);
printf("\n");
}
int main () {
int t = 1;
scanf("%d", &t);
while (t --) init();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 7924kb
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: 7920kb
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: 110ms
memory: 8064kb
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: 115ms
memory: 26040kb
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: 371ms
memory: 40352kb
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: 381ms
memory: 39796kb
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: 396ms
memory: 40124kb
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: 333ms
memory: 40000kb
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: 145ms
memory: 40256kb
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: 140ms
memory: 39476kb
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: 371ms
memory: 40128kb
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: 373ms
memory: 40120kb
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: 108ms
memory: 8012kb
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: 103ms
memory: 10292kb
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 2nd lines differ - expected: '101100000001011101100010000100...1000001101000100110000000010000', found: '101100001001011101110010001101...1100011101000100110000000010100'