QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#555873	#9251. Graph Changing	JZYZ^#	WA	4ms	3960kb	C++14	2.2kb	2024-09-10 11:25:58	2024-09-10 11:25:58

Judging History

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

[2024-09-10 11:25:58]
评测

测评结果：WA
用时：4ms
内存：3960kb

查看

[2024-09-10 11:25:58]
提交

answer

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

typedef long long LL ;
const int N = 1e5+10 ;

int q ;
int t , n , K , x , y ;

int f[50][50] , g[50][50] ;
void pusher()
{
	memset( f , 0x3f , sizeof f ) ;
	for(int j = 1 ; j < n ; j ++ ) {
		f[j][j+1] = f[j+1][j] = 1 ;
		f[j][j] = 0 ;
	}
	f[n][n] = 0 ;
	bool fg = 0 ;
	for(int i = 0 ; i <= t ; i ++ ) {
		fg = 0 ;
		if( i == 0 ) memcpy( g , f , sizeof g ) ;
		else {
			memset( g , 0x3f , sizeof g ) ;
			for(int i = 1 ; i <= n ; i ++ ) {
				for(int j = 1 ; j <= n ; j ++ ) {
					if( f[i][j] >= K ) {
						g[i][j] = 1 ;
					}
				}
				g[i][i] = 0 ;
			}
		}
 		for(int k = 1 ; k <= n ; k ++ ) {
			for(int i = 1 ; i <= n ; i ++ ) {
				for(int j = 1 ; j <= n ; j ++ ) {
					g[i][j] = min( g[i][j] , g[i][k]+g[k][j] ) ;
				} 
			}
		}
		memcpy( f , g , sizeof f ) ;
		for(int i = 1 ; i <= n ; i ++ ) {
			for(int j = 1 ; j <= n ; j ++ ) {
				if( i == j ) continue ;
				if( f[i][j] >= 10 ) {
					f[i][j] = -1 ;
				}
				else fg = 1 ;
			}
		}
		if( !fg ) {
			printf("-1\n") ;
			return ;
		}
	}
	if( f[x][y] <= 10 ) printf("%d\n" , f[x][y] ) ;
	else printf("-1\n") ;
}

int main()
{
	scanf("%d" , &q ) ;
	while( q -- ) {
		scanf("%d%d%d%d%d" , &t , &n , &K , &x , &y ) ;
		if( K == 1 ) {
			if( t == 0 ) printf("%d\n" , abs(x-y) ) ;
			else printf("1\n") ;
			continue ;
		}
		if( K == 2 ) {
			if( n >= 5 ) {
				if( t&1 ) printf("%d\n" , abs(x-y)==1?2:1 ) ;
				else printf("%d\n" , abs(x-y) ) ; 
			}
			else if( n == 4 ) {
				if( t&1 ) {
					if( (x==2&&y==3)||(x==3&&y==2) ) printf("3\n") ;
					else if( abs(x-y) == 1 ) printf("2\n") ;
					else printf("1\n") ;
				}
				else printf("%d\n" , abs(x-y) ) ; 
			}
			else if( n == 3 ) {
				if( t >= 2 ) printf("-1\n") ;
				else if( t == 1 ) printf("%d\n" , ((x==1&&y==3)||(x==3&&y==1))?1:-1 ) ;
				else printf("%d\n" , abs(x-y) ) ;
			}
			else {
				printf("%d\n" , t?-1:1 ) ;
			}
			continue ;
		}
		if( n <= 40 ) {
			pusher() ;
			continue ;
		}
		if( K >= 3 ) {
			if( t == 0 ) printf("%d\n" , abs(x-y) ) ;
			else if( t == 1 ) printf("%d\n" , abs(x-y)<K?2:1 ) ;
			else printf("-1\n") ;
			continue ;
		}
	}
	return 0 ;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 3896kb

input:

output:

result:

ok 5 lines

Test #2:

score: 0

Accepted

time: 0ms

memory: 3960kb

input:

output:

1
-1
-1
-1
-1
-1
1
-1
-1
-1
-1
-1
1
-1
-1
-1
-1
-1
1
-1
-1
-1
-1
-1
1
-1
-1
-1
-1
-1

result:

ok 30 lines

Test #3:

score: 0

Accepted

time: 0ms

memory: 3808kb

input:

output:

1
1
1
-1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1
1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1
1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1
1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1
1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1

result:

ok 90 lines

Test #4:

score: 0

Accepted

time: 0ms

memory: 3804kb

input:

output:

1
1
1
1
1
1
2
1
1
3
1
2
-1
-1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1
1
1
1
1
1
1
2
3
1
2
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1
1
1
1
1
1
2
1
1
3
1
2
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1
1
1
1
1
1
1...

result:

ok 180 lines

Test #5:

score: 0

Accepted

time: 1ms

memory: 3884kb

input:

output:

1
1
1
1
1
1
1
1
1
1
2
1
1
1
2
1
1
2
1
2
2
-1
1
1
-1
3
1
-1
-1
2
-1
-1
-1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1
1
1
1
1
1
1
1
1
1
1
2
3
4
1
2
3
1
2
1
-1
-1
-1
-1
-1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 300 lines

Test #6:

score: 0

Accepted

time: 1ms

memory: 3772kb

input:

output:

result:

ok 450 lines

Test #7:

score: 0

Accepted

time: 1ms

memory: 3880kb

input:

output:

result:

ok 630 lines

Test #8:

score: 0

Accepted

time: 2ms

memory: 3960kb

input:

output:

result:

ok 840 lines

Test #9:

score: 0

Accepted

time: 0ms

memory: 3892kb

input:

output:

result:

ok 1080 lines

Test #10:

score: 0

Accepted

time: 3ms

memory: 3880kb

input:

1350
1 10 1 1 2
1 10 1 1 3
1 10 1 1 4
1 10 1 1 5
1 10 1 1 6
1 10 1 1 7
1 10 1 1 8
1 10 1 1 9
1 10 1 1 10
1 10 1 2 3
1 10 1 2 4
1 10 1 2 5
1 10 1 2 6
1 10 1 2 7
1 10 1 2 8
1 10 1 2 9
1 10 1 2 10
1 10 1 3 4
1 10 1 3 5
1 10 1 3 6
1 10 1 3 7
1 10 1 3 8
1 10 1 3 9
1 10 1 3 10
1 10 1 4 5
1 10 1 4 6
1 10 1...

output:

result:

ok 1350 lines

Test #11:

score: -100

Wrong Answer

time: 4ms

memory: 3892kb

input:

1650
1 11 1 1 2
1 11 1 1 3
1 11 1 1 4
1 11 1 1 5
1 11 1 1 6
1 11 1 1 7
1 11 1 1 8
1 11 1 1 9
1 11 1 1 10
1 11 1 1 11
1 11 1 2 3
1 11 1 2 4
1 11 1 2 5
1 11 1 2 6
1 11 1 2 7
1 11 1 2 8
1 11 1 2 9
1 11 1 2 10
1 11 1 2 11
1 11 1 3 4
1 11 1 3 5
1 11 1 3 6
1 11 1 3 7
1 11 1 3 8
1 11 1 3 9
1 11 1 3 10
1 11...

output:

result:

wrong answer 120th lines differ - expected: '1', found: '2'