QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#37723#1195. One-Way ConveyorsclaesWA 19ms5908kbC++4.7kb2022-07-02 16:10:302022-07-02 16:10:32

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-07-02 16:10:32]
  • 评测
  • 测评结果:WA
  • 用时:19ms
  • 内存:5908kb
  • [2022-07-02 16:10:30]
  • 提交

answer

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std ;
int n , m , l ;
int fir[10010] , nxt[200010] ;
short zx[200010] ;
int bs ;
bool gb[200010] , fw[200010] ;
short col[10010] , co = 0 ;
short dfn[10010] , low[10010] , tim ;
short fir1[10010] , nxt1[20010] , zx1[20010] , bs1 ;
short sq[10010] , sz[10010] ;
short upz[10010] , upf[10010] , dnz[10010] , dnf[10010] ;
short q[10010] , z[10010] , ll ;
short fa[10010] , sd[10010] ;
short dp[25][10010] ;
void dfs( int wz , int fa )
{
	low[wz] = dfn[wz] = ++tim ;
//	cout<< wz << ' ' << fa << ' ' << dfn[wz] << endl ;
	for( int i = fir[wz] ; i != -1 ; i = nxt[i] )
	{
		if( zx[i] == fa ) continue ;
		if( dfn[zx[i]] == 0 )
		{
			dfs( zx[i] , wz ) ;
			low[wz] = min( low[wz] , low[zx[i]] ) ;
			if( low[zx[i]] > low[wz] )
			{
				gb[i] = gb[i ^ 1] = 1 ;
			}
		}
		else
		{
			low[wz] = min( low[wz] , dfn[zx[i]] ) ;
		}
	}
	return ;
}
void dfs1( int wz , int fa , int coo )
{
	col[wz] = coo ;
	for( int i = fir[wz] ; i != -1 ; i = nxt[i] )
	{
		if( fw[i] == 1 ) continue ;
		if( zx[i] == fa ) continue ;
		if( gb[i] == 1 ) continue ;
		q[ll] = wz ;
		z[ll] = zx[i] ;
		ll ++ ;
		fw[i] = fw[i ^ 1] = 1 ;
		if( col[zx[i]] == 0 ) dfs1( zx[i] , wz , coo ) ;
	}
	return ;
}
bool lll = false ;
bool ff[10010] ;
void dfs2( int wz )
{
	if( wz == 0 ) lll = true ;
	if( ff[wz] )
	{
		cout<< wz << ' ' << fa[wz] << endl ;
		lll = true ;
		return ;
	}
	ff[wz] = 1 ;
	for( int i = fir1[wz] ; i != -1 ; i = nxt1[i] )
	{
		if( zx1[i] == fa[wz] ) continue ;
		fa[zx1[i]] = wz ;
		sd[zx1[i]] = sd[wz] + 1 ;
		dfs2( zx1[i] ) ;
	}
	return ;
}
void lca( int a , int b )
{
	int ta = a ;
	int tb = b ;
	if( sd[a] > sd[b] )
	{
		for( int i = 19 ; i >= 0 ; i -- )
		{
			if( dp[i][a] == -1 ) continue ;
			if( sd[dp[i][a]] > sd[b] )
			{
				a = dp[i][a] ;
			}
		}
		if( fa[a] == b )
		{
			upz[a] += 1 ;
			upf[ta] += -1 ;
//			cout<< 'U' << ta << ' ' << a << endl ;
			return ;
		}
		a = fa[a] ;
	}
	if( sd[b] > sd[a] )
	{
		for( int i = 19 ; i >= 0 ; i -- )
		{
			if( dp[i][b] == -1 ) continue ;
			if( sd[dp[i][b]] > sd[a] )
			{
				b = dp[i][b] ;
			}
		}
//	cout<< a << ' ' << b << endl ;
		if( fa[b] == a )
		{
			dnz[b] += 1 ;
			dnf[tb] += -1 ;
//			cout<< 'D' << tb << ' ' << b << endl ;
			return ;
		}
		b = fa[b] ;
	}
	for( int i = 19 ; i >= 0 ; i -- )
	{
		if( dp[i][a] != dp[i][b] )
		{
			a = dp[i][a] ;
			b = dp[i][b] ;
		}
	}
	upz[a] += 1 ;
	upf[ta] += -1 ;
	dnz[b] += 1 ;
	dnf[tb] += -1 ;
	return ;
}
bool flag = true ;
void dfs3( int wz , int ujs , int djs )
{
//	cout<< wz << ' ' << fa[wz] << ' ' << ujs << ' ' << djs << endl ;
	int uu , dd ;
	ujs += upf[wz] ;
	djs += dnf[wz] ;
	for( int i = fir1[wz] ; i != -1 ; i = nxt1[i] )
	{
		if( zx1[i] == fa[wz] ) continue ;
		uu = ujs + upz[zx1[i]] ;
		dd = djs + dnz[zx1[i]] ;
		if( uu > 0 && dd > 0 )
		{
			flag = false ;
			return ;
		}
		if( uu > 0 )
		{
			q[ll] = sz[i] ;
			z[ll] = sq[i] ;
			ll ++ ;
		}
		else
		{
			q[ll] = sq[i] ;
			z[ll] = sz[i] ;
			ll ++ ;
		}
		dfs3( zx1[i] , uu , dd ) ;
	}
	return ;
}
int main ()
{
	memset( fir , -1 , sizeof(fir) ) ;
	memset( fir1 , -1 , sizeof(fir1) ) ;
	int t1 , t2 ;
	scanf( "%d%d" , &n , &m ) ;
	for( int i = 0 ; i < m ; i ++ )
	{
		scanf( "%d%d" , &t1 , &t2 ) ;
		t1 -- ;
		t2 -- ;
//		if( t1 == t2 ) return 1 ;
		nxt[bs] = fir[t1] ;
		fir[t1] = bs ;
		zx[bs] = t2 ;
		bs ++ ;
		nxt[bs] = fir[t2] ;
		fir[t2] = bs ;
		zx[bs] = t1 ;
		bs ++ ;
	}
	dfs( 0 , -1 ) ;
	for( int i = 0 ; i < n ; i ++ )
	{
		if( col[i] == 0 ) dfs1( i , -1 , ++ co ) ;
	}
	for( int i = 0 ; i < n ; i ++ )
	{
		for( int j = fir[i] ; j != -1 ; j = nxt[j] )
		{
			if( col[i] != col[zx[j]] )
			{
				nxt1[bs1] = fir1[col[i]] ;
				fir1[col[i]] = bs1 ;
				zx1[bs1] = col[zx[j]] ;
				sq[bs1] = i ;
				sz[bs1] = zx[j] ;
				bs1 ++ ;
			}
		}
	}
	fa[1] = -1 ;
	dfs2( 1 ) ;
	if( lll ) return 0 ;
	for( int i = 1 ; i <= co ; i ++ )
	{
//		cout<< col[i] << ' ' ;
		dp[0][i] = fa[i] ;
//		cout<< dp[0][i] << ' ' ;
	}
//	cout<< endl ;
	for( int j = 1 ; j < 20 ; j ++ )
	{
		for( int i = 1 ; i <= co ; i ++ )
		{
			if( dp[j - 1][i] != -1 )
			{
				dp[j][i] = dp[j - 1][dp[j - 1][i]] ;
			}
		}
	}
	scanf( "%d" , &l ) ;
	for( int i = 0 ; i < l ; i ++ )
	{
		scanf( "%d%d" , &t1 , &t2 ) ;
		t1 -- ;
		t2 -- ;
		if( col[t1] == col[t2] ) continue ;
		lca( col[t1] , col[t2] ) ;
	}
//	cout<< 1111 << endl ;
	dfs3( 1 , 0 , 0 ) ;
	if( flag )
	{
		printf( "Yes\n" ) ;
	}
	else
	{
		printf( "No\n" ) ;
		return 0 ;
	}
	for( int i = 0 ; i < ll ; i ++ )
	{
		printf( "%d %d\n" , q[i] + 1 , z[i] + 1 ) ;
	}
	return 0 ;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3944kb

input:

3 2
1 2
2 3
3
1 2
1 3
2 3

output:

Yes
1 2
2 3

result:

ok OK!

Test #2:

score: 0
Accepted
time: 3ms
memory: 5684kb

input:

3 2
1 2
2 3
3
1 2
1 3
3 2

output:

No

result:

ok OK!

Test #3:

score: 0
Accepted
time: 1ms
memory: 3892kb

input:

4 4
1 2
1 3
1 4
2 3
7
1 2
1 3
1 4
2 1
2 3
3 1
3 2

output:

Yes
1 3
3 2
2 1
1 4

result:

ok OK!

Test #4:

score: 0
Accepted
time: 19ms
memory: 4896kb

input:

9990 47670
134 2450
4227 9100
1861 9948
120 8957
1161 4767
76 1714
5207 5838
2726 8974
2489 8619
2379 4933
3675 9554
344 3215
1654 6168
5630 6614
3247 5202
4456 5373
4380 6605
2626 4064
2194 6332
2749 9719
360 5059
7967 8835
5433 6494
497 6638
5945 9063
7576 7879
3550 4107
83 2891
3107 6917
2089 689...

output:

No

result:

ok OK!

Test #5:

score: 0
Accepted
time: 13ms
memory: 4232kb

input:

3219 13421
762 2133
1106 2880
2287 2476
313 992
741 1903
811 2050
1468 2184
3031 3037
403 1855
1060 1415
1792 2804
772 2956
140 2281
808 1953
895 1731
1217 1551
1264 1885
749 1082
1564 2824
1549 1741
1966 2730
112 2825
158 2625
2128 2917
128 3032
644 3194
1634 2743
1545 1961
2402 2680
2663 2814
1040...

output:

No

result:

ok OK!

Test #6:

score: 0
Accepted
time: 11ms
memory: 5908kb

input:

8013 18891
6127 6374
3969 4617
215 2699
268 6282
167 5415
1318 6256
3994 6192
4325 7186
1785 4188
6570 7153
772 5901
9 5190
873 6509
161 7476
2960 2966
4598 7170
1157 3798
758 4508
1446 5205
445 5989
686 5479
669 4711
6254 6860
1722 7020
463 3494
5063 7309
2231 6762
1208 4304
4789 5081
3925 6248
107...

output:

No

result:

ok OK!

Test #7:

score: -100
Wrong Answer
time: 11ms
memory: 4660kb

input:

9968 46595
3655 5544
5747 9340
6020 9528
5789 9882
4609 8832
1969 5167
2610 8012
324 9387
694 3647
3667 8483
4202 4963
2643 8104
1139 9679
1407 7022
9031 9944
5183 8744
3341 3858
326 2610
414 1317
657 7942
4702 5671
2072 3200
3074 3597
26 3728
288 7757
144 9580
1374 2065
2683 8068
1341 6526
2140 257...

output:

No

result:

wrong answer Output doesn't match the expected answer