QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#608574#9251. Graph ChangingpropaneWA 1ms3856kbC++204.8kb2024-10-03 23:20:162024-10-03 23:20:17

Judging History

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

  • [2024-10-03 23:20:17]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3856kb
  • [2024-10-03 23:20:16]
  • 提交

answer

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
using LL = long long;

int main(){

#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    int T;
    cin >> T;
    while(T--){
        int t, n, k, x, y;
        cin >> t >> n >> k >> x >> y;
        if (x > y) swap(x, y);
        if (k == 1){
            if (t == 0){
                cout << y - x << '\n';
            }
            else{
                cout << 1 << '\n';
            }
        }
        else if (n == 2){
            if (t == 0){
                cout << y - x << '\n';
            }
            else{
                cout << -1 << '\n';
            }
        }
        else if (k == 2){
            if (n == 3){
                if (t == 0){
                    cout << y - x << '\n';
                }
                else if (t == 1){
                    if (x == 1 and y == 3){
                        cout << 1 << '\n';
                    }
                    else{
                        cout << -1 << '\n';
                    }
                }
                else{
                    cout << -1 << '\n';
                }
            }
            else if (t % 2 == 0){
                cout << y - x << '\n';
            }
            else{
                if (y - x >= 2){
                    cout << 1 << '\n';
                }
                else if (n - x >= k and n - y >= k){
                    cout << 2 << '\n';
                }
                else if (x - 1 >= k and y - 1 >= k){
                    cout << 2 << '\n';
                }
                else{
                    cout << 3 << '\n';
                }
            }
        }
        else{
            if (n <= 5){
                const int INF = 1e9;
                vector<pair<int, int > > edge;
                for(int i = 1; i + 1 <= n; i++){
                    edge.push_back({i, i + 1});
                }

                auto get = [&](){
                    vector<vector<int> > d(n + 1, vector<int>(n + 1, INF));
                    for(int i = 1; i <= n; i++){
                        d[i][i] = 0;
                    }
                    for(auto [x, y] : edge){
                        d[x][y] = d[y][x] = 1;
                    }
                    for(int k = 1; k <= n; k++){
                        for(int i = 1; i <= n; i++){
                            for(int j = 1; j <= n; j++){
                                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
                            }
                        }
                    }
                    vector<pair<int, int> > ans;
                    for(int i = 1; i <= n; i++){
                        for(int j = i + 1; j <= n; j++){
                            if (d[i][j] != INF and d[i][j] >= k){
                                ans.push_back({i, j});
                            }
                        }
                    }
                    edge.swap(ans);
                };

                auto dis = [&](int x, int y){
                    vector<vector<int> > d(n + 1, vector<int>(n + 1, INF));
                    for(int i = 1; i <= n; i++){
                        d[i][i] = 0;
                    }
                    for(auto [x, y] : edge){
                        d[x][y] = d[y][x] = 1;
                    }
                    for(int k = 1; k <= n; k++){
                        for(int i = 1; i <= n; i++){
                            for(int j = 1; j <= n; j++){
                                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
                            }
                        }
                    }
                    return d[x][y] == INF ? -1 : d[x][y];                   
                };

                for(int i = 0; i < t and !edge.empty(); i++) get();
                cout << dis(x, y) << '\n';
            }
            else if (t == 0){
                cout << y - x << '\n';
            }
            else if (t > 1){
                cout << -1 << '\n';
            }
            else{
                if (max(x - 1, n - x) < k or max(y - 1, n - y) < k){
                    cout << -1 << '\n';
                }
                else{
                    if (y - x >= k){
                        cout << 1 << '\n';
                    }
                    else if (n - x >= k and n - y >= k){
                        cout << 2 << '\n';
                    }
                    else if (x - 1 >= k and y - 1 >= k){
                        cout << 2 << '\n';
                    }
                    else{
                        cout << 3 << '\n';
                    }
                }
            }
        }
    }

}

詳細信息

Test #1:

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

input:

5
1 5 3 2 4
1 10 4 2 4
2 10 5 2 4
1 3 2 1 3
1 3 2 1 2

output:

3
2
-1
1
-1

result:

ok 5 lines

Test #2:

score: 0
Accepted
time: 1ms
memory: 3556kb

input:

30
1 2 1 1 2
1 2 2 1 2
1 2 3 1 2
1 2 4 1 2
1 2 5 1 2
1 2 6 1 2
2 2 1 1 2
2 2 2 1 2
2 2 3 1 2
2 2 4 1 2
2 2 5 1 2
2 2 6 1 2
3 2 1 1 2
3 2 2 1 2
3 2 3 1 2
3 2 4 1 2
3 2 5 1 2
3 2 6 1 2
4 2 1 1 2
4 2 2 1 2
4 2 3 1 2
4 2 4 1 2
4 2 5 1 2
4 2 6 1 2
5 2 1 1 2
5 2 2 1 2
5 2 3 1 2
5 2 4 1 2
5 2 5 1 2
5 2 6 1 2

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

input:

90
1 3 1 1 2
1 3 1 1 3
1 3 1 2 3
1 3 2 1 2
1 3 2 1 3
1 3 2 2 3
1 3 3 1 2
1 3 3 1 3
1 3 3 2 3
1 3 4 1 2
1 3 4 1 3
1 3 4 2 3
1 3 5 1 2
1 3 5 1 3
1 3 5 2 3
1 3 6 1 2
1 3 6 1 3
1 3 6 2 3
2 3 1 1 2
2 3 1 1 3
2 3 1 2 3
2 3 2 1 2
2 3 2 1 3
2 3 2 2 3
2 3 3 1 2
2 3 3 1 3
2 3 3 2 3
2 3 4 1 2
2 3 4 1 3
2 3 4 2...

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

input:

180
1 4 1 1 2
1 4 1 1 3
1 4 1 1 4
1 4 1 2 3
1 4 1 2 4
1 4 1 3 4
1 4 2 1 2
1 4 2 1 3
1 4 2 1 4
1 4 2 2 3
1 4 2 2 4
1 4 2 3 4
1 4 3 1 2
1 4 3 1 3
1 4 3 1 4
1 4 3 2 3
1 4 3 2 4
1 4 3 3 4
1 4 4 1 2
1 4 4 1 3
1 4 4 1 4
1 4 4 2 3
1 4 4 2 4
1 4 4 3 4
1 4 5 1 2
1 4 5 1 3
1 4 5 1 4
1 4 5 2 3
1 4 5 2 4
1 4 5 ...

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

input:

300
1 5 1 1 2
1 5 1 1 3
1 5 1 1 4
1 5 1 1 5
1 5 1 2 3
1 5 1 2 4
1 5 1 2 5
1 5 1 3 4
1 5 1 3 5
1 5 1 4 5
1 5 2 1 2
1 5 2 1 3
1 5 2 1 4
1 5 2 1 5
1 5 2 2 3
1 5 2 2 4
1 5 2 2 5
1 5 2 3 4
1 5 2 3 5
1 5 2 4 5
1 5 3 1 2
1 5 3 1 3
1 5 3 1 4
1 5 3 1 5
1 5 3 2 3
1 5 3 2 4
1 5 3 2 5
1 5 3 3 4
1 5 3 3 5
1 5 3 ...

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

input:

450
1 6 1 1 2
1 6 1 1 3
1 6 1 1 4
1 6 1 1 5
1 6 1 1 6
1 6 1 2 3
1 6 1 2 4
1 6 1 2 5
1 6 1 2 6
1 6 1 3 4
1 6 1 3 5
1 6 1 3 6
1 6 1 4 5
1 6 1 4 6
1 6 1 5 6
1 6 2 1 2
1 6 2 1 3
1 6 2 1 4
1 6 2 1 5
1 6 2 1 6
1 6 2 2 3
1 6 2 2 4
1 6 2 2 5
1 6 2 2 6
1 6 2 3 4
1 6 2 3 5
1 6 2 3 6
1 6 2 4 5
1 6 2 4 6
1 6 2 ...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
1
1
1
1
2
1
1
1
2
1
1
2
1
2
2
2
1
1
1
2
3
1
1
3
3
1
2
2
2
2
-1
-1
1
1
-1
-1
3
1
-1
-1
-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
1
1
1
1
1
2
3
4
5
1
2
3
4
1
2
3
1
2
1
-1
-1
-1
-1
-1
-1
-1
-...

result:

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