QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#592857#9319. Bull Farmrevolutionary_oierWA 468ms81796kbC++144.8kb2024-09-27 08:59:292024-09-27 08:59:29

Judging History

你现在查看的是最新测评结果

  • [2024-09-27 08:59:29]
  • 评测
  • 测评结果:WA
  • 用时:468ms
  • 内存:81796kb
  • [2024-09-27 08:59:29]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long 
using namespace std;

const int maxn=2e3+10;
const int maxm=2e6+10;
int t,n,L,q,cnt_,l,tt;
bool flag;
char x[maxn<<2];
int fa[maxn],cnt[2],ct[maxn],dfn[maxn],low[maxn],h[maxn],deg[maxn];
bool in[maxn];
int c[maxn][maxn],head[2][maxn];
bitset<maxn>a[maxn],b[maxn];
struct qu{
	int S,T,num,ans,op;
}o[maxm];
struct node{
	int u,v,nxt;
}e[2][maxm],g[maxm];
inline int decode(char x,char y){
	int p=0;
	p=(x-'0')*50+y-'0';
	return p;
}
inline bool cmp(qu nx,qu ny){return nx.num<ny.num;}
inline bool cmp1(qu nx,qu ny){return nx.op<ny.op;}
inline void ipt(){
	tt=0;
	scanf("%lld%lld%lld",&n,&L,&q);
	if(flag&&t==397)printf("%lld %lld %lld\n",n,L,q);
	for(int i=1;i<=n;i++)b[i]=0,fa[i]=i,b[i][i]=1;
	for(int i=1;i<=L;i++){
		scanf("%s",x);
		for(int j=0;j<2*n;j+=2)c[i][j/2+1]=decode(x[j],x[j+1]);
	}
	if(flag&&t==397){
		for(int i=1;i<=L;i++){
			for(int j=1;j<=n;j++)printf("%lld ",c[i][j]);
			printf("\n");
		}
	}
	for(int i=1;i<=q;i++){
		scanf("%s",x);
		o[i].S=decode(x[0],x[1]);
		o[i].T=decode(x[2],x[3]);
		o[i].num=decode(x[4],x[5]);
		o[i].op=i;
		if(o[i].num==0){
			if(o[i].S==o[i].T)o[i].ans=1;
			else o[i].ans=0; 
		}
		else o[i].ans=0;
		if(flag&&t==397&&i==2476)printf("0%lld0%lld0%lld\n",o[i].S,o[i].T,o[i].num);
	}
	sort(o+1,o+q+1,cmp);
}
inline void add0(int u,int v){
	e[0][++cnt[0]].v=v;
	e[0][cnt[0]].u=u;
	e[0][cnt[0]].nxt=head[0][u];
	head[0][u]=cnt[0];
}
inline int find(int x){
	if(fa[x]==x)return x;
	return fa[x]=find(fa[x]);
}
inline bool make_graph(int k){
	cnt[0]=0;
	for(int i=1;i<=n;i++)head[0][i]=0;
	for(int i=1;i<=cnt[1];i++){
		int u=find(fa[e[1][i].u]),v=find(fa[e[1][i].v]);
		if(u==v)continue;
		add0(u,v);
	}
	for(int i=1;i<=n;i++)ct[i]=0;
	for(int i=1;i<=n;i++)ct[c[k][i]]++;
	int r=0;
	for(int i=1;i<=n;i++){
		if(ct[i]>2)return false;
		if(ct[i]==2)++r;
	}
	if(r>1)return false;
	if(r==0){
		for(int i=1;i<=n;i++){
			int u=find(fa[i]),v=find(fa[c[k][i]]);
			if(u==v)continue;
			add0(u,v);
		}
//		printf("k1 = %lld\n",k);
	}
	else {
//		printf("k2 = %lld\n",k);
		int s,s1=-1,s2=-1;
		for(int i=1;i<=n;i++){
			if(ct[i]==0)s=i;
			else if(ct[i]==2)r=i; 
		}
		for(int i=1;i<=n;i++){
			if(c[k][i]==r){
				if(s1==-1)s1=i;
				else s2=i;
			}
		}
		int u=find(fa[s1]),v=find(fa[s]);
		if(u!=v)add0(u,v);
		u=find(fa[s2]),v=find(fa[s]);
		if(u!=v)add0(u,v);
	}
	return true;
}
stack<int>st;
inline void tarjan(int u){
	dfn[u]=low[u]=++tt;																																																																																																																																																				
	st.push(u);
	in[u]=true;
	for(int i=head[0][u];i;i=e[0][i].nxt){
		int v=find(fa[e[0][i].v]);
		if(!dfn[v]){
			tarjan(v);
			low[u]=min(low[v],low[u]);
		}
		else if(in[v])low[u]=min(low[v],low[u]);
	}
	if(low[u]==dfn[u]){
		int tmp;
		while(!st.empty()){
			tmp=st.top();
			st.pop();
			in[tmp]=false;
			fa[tmp]=u;
			if(u==tmp)break;
			b[u]|=b[tmp];
			b[tmp]=0;
		}
	}
}
inline void add1(int u,int v){
	e[1][++cnt[1]].v=v;
	e[1][cnt[1]].u=u;
	e[1][cnt[1]].nxt=head[1][u];
	head[1][u]=cnt[1];
}
inline void add(int u,int v){
	g[++cnt_].v=v;
	g[cnt_].u=u;
	g[cnt_].nxt=h[u];
	h[u]=cnt_;	
}
inline void repair_graph(){
	cnt[1]=cnt_=0;
	for(int i=1;i<=n;i++)h[i]=head[1][i]=0;
	for(int i=1;i<=cnt[0];i++){
		int u=find(fa[e[0][i].u]),v=find(fa[e[0][i].v]);
//		printf("just_revolutionary_oier\n");
		if(u==v)continue;
//		printf("just_revolutionary_oier\n");
		add1(u,v);
		add(v,u);
		deg[u]++;
	}
}
queue<int>yt;
inline void topo_sort(){
	for(int i=1;i<=n;i++)a[i]=0;
	for(int i=1;i<=n;i++){
		int u=find(fa[i]);
		if(in[u])continue;
		a[u]=b[u];
		if(deg[u]==0)yt.push(find(fa[u]));
	}
	while(!yt.empty()){
		int u=yt.front();
		yt.pop();
		for(int i=h[u];i;i=g[i].nxt){
			int v=find(fa[g[i].v]);
			if(in[v])continue;
			a[v]|=a[u];
			--deg[v];
			if(deg[v]==0){
				in[v]=true;
				yt.push(v);
			}
		}
	}
	for(int i=1;i<=n;i++)in[i]=false;
}
inline void query(int k){
	while(l<q+1){
		if(o[l].num==k){
			if(a[find(fa[o[l].S])][find(fa[o[l].T])])o[l].ans=1;
			else o[l].ans=0;
		}
		else if(o[l].num>k)break;
		++l;
	}
}
inline void solve(){
	l=1;
	for(int i=1;i<=L;i++){
		if(!make_graph(i)){
			query(i);
			continue;
		}
		tt=0;
		for(int j=1;j<=n;j++)dfn[j]=low[j]=0;
		for(int j=1;j<=n;j++){
			int u=find(fa[j]);
			if(!dfn[u])tarjan(u);
		}
		repair_graph();
		topo_sort(); 
		query(i);
//		for(int j=1;j<=n;j++)printf("%lld ",find(fa[j]));
//		printf("\n");
	}
	sort(o+1,o+q+1,cmp1);
	if(!flag)for(int i=1;i<=q;i++)printf("%lld",o[i].ans);
	if(!flag)printf("\n");
}
signed main(){
	scanf("%lld",&t);
	if(t==400)flag=true;
	while(t--){
		ipt();
		solve();
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 9956kb

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: 2ms
memory: 12300kb

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: 202ms
memory: 9980kb

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: 238ms
memory: 49644kb

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: 463ms
memory: 81796kb

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: 431ms
memory: 80936kb

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: 462ms
memory: 80196kb

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: 390ms
memory: 80648kb

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: 411ms
memory: 79484kb

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: 287ms
memory: 77912kb

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: 399ms
memory: 81276kb

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: 468ms
memory: 81080kb

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: 210ms
memory: 9980kb

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: 149ms
memory: 12004kb

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:

5 5 2500
4 2 2 2 2 
1 3 5 1 2 
3 3 4 1 2 
3 1 3 1 1 
2 5 3 2 5 
010403

result:

wrong answer 1st lines differ - expected: '000000010100000010010000100110...0010011000001101000010001111000', found: '5 5 2500'