QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#37716 | #1195. One-Way Conveyors | claes | WA | 12ms | 4712kb | C++ | 4.8kb | 2022-07-02 15:58:27 | 2022-07-02 15:58:27 |
Judging History
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