QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#37716#1195. One-Way ConveyorsclaesWA 12ms4712kbC++4.8kb2022-07-02 15:58:272022-07-02 15:58:27

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 15:58:27]
  • 评测
  • 测评结果:WA
  • 用时:12ms
  • 内存:4712kb
  • [2022-07-02 15:58:27]
  • 提交

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 ;
//	cout<< wz << ' ' << col[wz] << endl ;
	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 -- ;
		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( gb[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 = 0 ; i < n ; i ++ )
//	{
//		cout<< col[i] << endl ;
//	}
	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 ;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 1ms
memory: 3756kb

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

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: -100
Wrong Answer
time: 12ms
memory: 4712kb

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:

211 211
1 211
1 1
229 229
1 229
93 93
229 93
53 53
271 271
53 271
146 146
271 146
53 53
155 53
193 193
53 193
53 53
155 155
39 39
155 39
16 16
39 16
148 148
16 148
23 23
37 23
96 96
148 96
148 148
16 16
36 36
254 254
44 254
16 36
85 85
98 85
36 98
32 32
39 32
97 97
32 97
33 33
97 33
50 50
165 165
50...

result:

wrong answer Output doesn't match the expected answer