QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#675435	#9251. Graph Changing	woodie_0064	WA	0ms	3784kb	C++20	2.4kb	2024-10-25 18:35:33	2024-10-25 18:35:33

Judging History

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

[2024-10-25 18:35:33]
评测

测评结果：WA
用时：0ms
内存：3784kb

查看

[2024-10-25 18:35:33]
提交

answer

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 1e5 + 3;
int T;
int n, num;


void work(){
	int q;cin >> q;
	while(q--) {
		int t,n,k,x,y;cin >> t >> n >> k >> x >> y;
		if(x < y) swap(x,y);
		if(t == 0) {
			cout << x - y << '\n';
			continue;
		}
		if(k == 1) {
			cout << "1\n";
			continue;
		}
		if(n == 2) {
			cout << "-1\n";
			continue;
		}
		if(n == 3) {
			if(k >= 3) cout << "-1\n";
			else if(k == 2){
				if(t > 1) cout << "-1\n";
				else {
					if(x == 2 || y == 2) cout << "-1\n";
					else cout << "1\n";
				}
			}
			continue;
		}
		if(k == 2) {
			if(t % 2 == 0) cout << x - y << '\n';
			else {
				if(n >= 5) cout << (x - y == 1 ? 2 : 1) << '\n';
				else {
					if(x == 3 && y == 2) cout << "3\n";
					else if(x - y == 1) cout << "2\n";
					else cout << "1\n";
				}
			}
			continue;
		}
		if(k == 3) {
			if(n >= 7) {
				if(t == 1) cout << (x - y >= k ? 1 : 2) << '\n';
				else cout << "-1\n";
			}else {
				t += 1;
				vector <vector <int>> f((n + 1),vector <int> (n + 1,1000));
				for(int i = 1;i < n;i++) f[i][i + 1] = f[i + 1][i] = 1;
				for(int i = 1;i <= n;i++) f[i][i] = 0;
				while(t--) {
					for(int i = 1;i <= n;i++) {
						for(int j = 1;j <= n;j++) {
							for(int k = 1;k <= n;k++) f[j][k] = min(f[j][k],f[j][i] + f[i][k]);
						}
					}
					if(t == 0) break;
					vector <vector <int>> g((n + 1),vector <int> (n + 1,1000));
					bool flag = false;
					for(int i = 1;i <= n;i++)  {
						for(int j = 1;j <= n;j++) {
							if(f[i][j] >= k) {
								g[i][j] = 1;
								flag = true;
							}
						}
					}
					f = g;
					for(int i = 1;i <= n;i++) f[i][i] = 0;
					if(!flag) break;
				}
				if(f[x][y] >= n) f[x][y] = -1;
				cout << f[x][y] << '\n';
			}
			continue;
		}
		if(k >= 4) {
			if(t != 1) cout << "-1\n";
			else {
				
				auto check = [&] (int x) {
					return x <= k && x > n - k;
				};
				
				if(x - y >= k) cout << "1\n";
				else if(check(x) || check(y)) cout << "-1\n";
				else {
					if(x <= n - k && y <= n - k)cout << "2\n";
					else if(x > k && y > k) cout << "2\n";
					else cout << "3\n";
				}
			}
			continue;
		}
	}
}


int main(){
//	freopen("test.txt", "r", stdin);
	ios::sync_with_stdio(false);
	cin.tie(0);
//	cin >> T;
//	while(T--){
		work();
//	}	
	return 0;
}

源文件, 语言: C++20

详细

Test #1:

score: 100

Accepted

time: 0ms

memory: 3552kb

input:

output:

result:

ok 5 lines

Test #2:

score: 0

Accepted

time: 0ms

memory: 3784kb

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

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: -100

Wrong Answer

time: 0ms

memory: 3556kb

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
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
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...

result:

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