QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#566638 | #9319. Bull Farm | ericmegalovania | WA | 181ms | 39332kb | C++20 | 3.9kb | 2024-09-16 00:54:45 | 2024-09-16 00:54:47 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ONLINE
#ifndef ONLINE
char DEBUG_BUFFER[1000];
#define debug(...) {sprintf(DEBUG_BUFFER,##__VA_ARGS__);cerr<<DEBUG_BUFFER;}
#else
#define debug(...) ;
#endif
using LL=long long;
using PII=pair<int,int>;
#define all(x) (x).begin(),(x).end()
#define allr(x) (x).rbegin(),(x).rend()
#define FAST_IO {ios::sync_with_stdio(false);cin.tie(nullptr);}
inline int read(){static int x; cin>>x; return x;}
inline LL readLL(){static LL x; cin>>x; return x;}
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
bitset<2001>key[2001];
void solve(){
int n=read(),m=read(),T=read();
vector<int>id(n+1);
iota(all(id),0);
vector a(m+1,vector<int>(n+1));
vector<array<int,4>>b(m+1,array<int,4>{-1,-1,-1,-1});
for(int i=1;i<=m;i++){
static string s; cin>>s;
vector<int>vis(n+1);
bool flag=1,ok=1;
for(int j=1,k=0;j<=n;j++){
a[i][j]=(s[k]-'0')*50+(s[k+1]-'0');
k+=2;
vis[a[i][j]]++;
if(vis[a[i][j]]>1) flag=0;
if(vis[a[i][j]]>=3) ok=0;
}
if(flag){
b[i]={0,0,0,0};
}
else if(ok){
int cnt=0,empty;
for(int j=1;j<=n;j++){
if(vis[j]==2) cnt++;
else if(!vis[j]) empty=j;
}
if(cnt==1){
b[i]={1,0,0,empty};
for(int j=1;j<=n;j++){
if(vis[a[i][j]]==2){
if(!b[i][1]) b[i][1]=j;
else b[i][2]=j;
}
}
}
}
}
vector<vector<int>>e(n+1);
auto addedge=[&](int u,int v)->void{
u=id[u],v=id[v];
if(u!=v) e[u].push_back(v);
};
vector<int>dfn,low,inStack,scc,siz;
int timStamp,col=n;
auto UPDATE=[&]()->void{
int N=col; timStamp=0,col=0;
dfn.assign(N+1,0);
low.assign(N+1,0);
inStack.assign(N+1,0);
scc.assign(N+1,0);
siz.assign(N+1,0);
stack<int,vector<int>>stk;
auto tarjan=[&](auto&& self,int u)->void{
low[u]=dfn[u]=++timStamp;
stk.push(u),inStack[u]=1;
for(auto v:e[u]){
if(!dfn[v]){
self(self,v);
low[u]=min(low[u],low[v]);
}
else if(inStack[v]){
low[u]=min(low[u],dfn[v]);
}
}
if(dfn[u]==low[u]){
++col;
while(stk.top()!=u){
siz[scc[stk.top()]=col]++;
inStack[stk.top()]=0; stk.pop();
}
siz[scc[stk.top()]=col]++;
inStack[stk.top()]=0; stk.pop();
}
};
for(int i=1;i<=N;i++){
if(!dfn[i]) tarjan(tarjan,i);
}
vector<vector<int>>adj(col+1);
for(int u=1;u<=N;u++){
for(auto v:e[u]){
if(scc[u]!=scc[v]){
adj[scc[u]].push_back(scc[v]);
}
}
}
for(int i=1;i<=col;i++){
sort(all(adj[i]));
adj[i].erase(unique(all(adj[i])),adj[i].end());
}
vector<int>vv(col+1);
auto dp=[&](auto&& self,int u)->void{
if(vv[u]) return;
vv[u]=1;
for(auto v:adj[u]){
self(self,v);
key[u]|=key[v];
}
};
for(int i=1;i<=col;i++){
key[i].reset();
key[i][i]=1;
}
for(int i=1;i<=col;i++){
dp(dp,i);
}
for(int i=1;i<=n;i++){
id[i]=scc[id[i]];
}
swap(e,adj);
};
vector<array<int,4>>q(T); //[a,b,c,id]
for(int i=0;i<T;i++){
static string s; cin>>s;
q[i][3]=i;
for(int j=0,k=0;j<3;j++){
q[i][j]=(s[k]-'0')*50+(s[k+1]-'0');
k+=2;
}
}
sort(all(q),[&](const array<int,4>& A,const array<int,4>& B)->bool{
return A[2]<B[2];
});
vector<int>ans(T);
int nw_c=1;
for(auto [aa,bb,c,iid]:q){
debug("%d %d %d %d\n",aa,bb,c,iid);
bool upd=0;
while(nw_c<=c){
debug("nw_c=%d\n",nw_c);
if(b[nw_c][0]==-1){
nw_c++;
continue;
}
if(b[nw_c][0]==0){
for(int j=1;j<=n;j++){
addedge(j,a[nw_c][j]);
}
}
else{
addedge(b[nw_c][1],b[nw_c][3]);
addedge(b[nw_c][2],b[nw_c][3]);
}
upd=1;
nw_c++;
}
if(upd){
UPDATE();
}
ans[iid]=key[id[aa]][id[bb]]|(aa==bb);
}
for(auto x:ans){
cout<<x;
}
cout<<"\n";
}
int main(){
FAST_IO;
for(int T=read();T--;) solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3620kb
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: 0ms
memory: 3548kb
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: 83ms
memory: 3720kb
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: 95ms
memory: 22928kb
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: 133ms
memory: 38848kb
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: 175ms
memory: 38988kb
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: 181ms
memory: 39084kb
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: 115ms
memory: 39332kb
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: 116ms
memory: 38852kb
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: 116ms
memory: 22884kb
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: 132ms
memory: 38836kb
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: 132ms
memory: 39168kb
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: 83ms
memory: 3720kb
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: 80ms
memory: 3676kb
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: '101100000001011101100010000100...1000001101000100110000000010000'