QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#37714#1195. One-Way ConveyorsclaesWA 10ms4684kbC++4.6kb2022-07-02 15:50:392022-07-02 15:50:42

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:50:42]
  • 评测
  • 测评结果:WA
  • 用时:10ms
  • 内存:4684kb
  • [2022-07-02 15:50:39]
  • 提交

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 ;
		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 = 1 ; i <= co ; 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: 3ms
memory: 3952kb

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: 0ms
memory: 3708kb

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: 3884kb

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: 10ms
memory: 4684kb

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:

211112291932295327153146271531551935353155391551639148162337961481481636254441685983632399732339750165501271512991762991512993051515291139191189761899118991127521659279266793259792061081087925979913720119012527212513752521654827252072514320725274827687068250702026848165312233102232232423117724213117...

result:

wrong answer Output doesn't match the expected answer