— Dark mode

Datatähti 2024 loppu

Peli

  • Start: 2024-01-20 13:00:00
  • End: 2024-01-20 17:00:00
Submission details
Task:Peli
Sender:perusjuntti
Submission time:2024-01-20 16:29:55 +0200
Language:C++ (C++11)
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
Test results
testverdicttimegroup
#10.08 s1, 2details
#20.08 s1, 2details
#30.63 s2details
#40.08 s1, 2details
#50.08 s1, 2details
#60.62 s2details
#70.62 s2details
#80.08 s1, 2details
#90.91 s2details
#100.93 s2details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:40:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   40 |             auto [s, d] = q.front(); q.pop();
      |                  ^

Code

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
using namespace std;

const int mxN = 2555;

vector<int> adj[mxN];
vector<vector<pair<int,int>>> dist_parity(mxN,vector<pair<int,int>>(mxN,{0,0}));
int shortest[mxN][mxN][2];
int vis[mxN];


signed main() {
    int n, m, q;
    cin >> n >> m >> q;

    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            shortest[i][j][0] = 1e10;
            shortest[i][j][1] = 1e10;
        }
    }

    //etsitään lyhimmät parillisen ja parittoman pituiset reitit alkusolmusta kaikkiin muihin solmuihin
    for (int i = 1; i <= n; ++i) {
        memset(vis,0,sizeof(vis));
        queue<pair<int,int>> q;
        q.push({i,0});

        while (q.size()) {
            auto [s, d] = q.front(); q.pop();

            if (d & 1) {
                dist_parity[i][s].se = 1;
                shortest[i][s][1] = min(shortest[i][s][1],d);
            }
            else {
                dist_parity[i][s].fi = 1;
                shortest[i][s][0] = min(shortest[i][s][0],d);
            }

            if (vis[s]) continue;
            vis[s] = 1;
            for (int u : adj[s])
                q.push({u,d+1});
        }   
    }


    for (int i = 0; i < q; ++i) {
        int a, b, x;
        cin >> a >> b >> x;

        cout << shortest[a][b][0] << ' ' << shortest[a][b][1] << '\n';
        if (x & 1) {
            if (dist_parity[a][b].se && x >= shortest[a][b][1])
                cout << "YES\n";
            else
                cout << "NO\n";
        }
        else {
            if (dist_parity[a][b].fi && x >= shortest[a][b][0])
                cout << "YES\n";
            else
                cout << "NO\n";
        }
    }
}

Test details

Test 1

Group: 1, 2

Verdict:

input
2 1 100
1 2
1 1 0
1 2 0
2 1 0
...
view save

correct output
YES
NO
NO
YES
NO
...
view save

user output
0 10000000000
YES
10000000000 1
NO
10000000000 1
...
Truncated

Test 2

Group: 1, 2

Verdict:

input
50 49 100
33 34
7 8
49 50
47 48
...
view save

correct output
NO
NO
NO
NO
NO
...
view save

user output
10000000000 15
NO
10000000000 3
NO
10000000000 21
...
Truncated

Test 3

Group: 2

Verdict:

input
2500 2499 100000
821 822
2351 2352
752 753
832 833
...
view save

correct output
NO
YES
YES
NO
NO
...
view save

user output
746 10000000000
NO
164 10000000000
YES
1064 10000000000
...
Truncated

Test 4

Group: 1, 2

Verdict:

input
12 12 100
9 10
2 3
1 12
1 2
...
view save

correct output
NO
NO
NO
NO
NO
...
view save

user output
10000000000 3
NO
10000000000 1
NO
10000000000 5
...
Truncated

Test 5

Group: 1, 2

Verdict:

input
11 11 100
10 11
7 8
1 2
5 6
...
view save

correct output
YES
YES
YES
YES
YES
...
view save

user output
4 10000000000
YES
10000000000 1
NO
6 5
...
Truncated

Test 6

Group: 2

Verdict:

input
2500 2500 100000
1936 1937
1884 1885
751 752
831 832
...
view save

correct output
NO
YES
YES
NO
NO
...
view save

user output
746 10000000000
NO
164 10000000000
YES
1064 10000000000
...
Truncated

Test 7

Group: 2

Verdict:

input
2499 2499 100000
821 822
2351 2352
752 753
832 833
...
view save

correct output
YES
YES
YES
YES
YES
...
view save

user output
746 10000000000
NO
164 10000000000
YES
10000000000 1063
...
Truncated

Test 8

Group: 1, 2

Verdict:

input
50 99 100
40 47
34 50
44 47
15 16
...
view save

correct output
YES
YES
YES
YES
YES
...
view save

user output
4 10000000000
YES
2 3
YES
4 3
...
Truncated

Test 9

Group: 2

Verdict:

input
2500 4999 100000
1191 2361
251 399
1026 2300
82 1655
...
view save

correct output
YES
YES
YES
YES
YES
...
view save

user output
6 7
YES
10000000000 5
NO
6 5
...
Truncated

Test 10

Group: 2

Verdict:

input
2500 4999 100000
2023 2218
23 51
1020 1272
11 114
...
view save

correct output
YES
YES
YES
YES
YES
...
view save

user output
6 7
YES
10000000000 5
YES
6 5
...
Truncated

Tasks

A Palindromi-B Sukat-C Sulut-D Peli-E Retkeily-F Polut-

Submissions (perusjuntti)

2024-01-20 16:29:55 0