oj.uz

Submission #1041052

# Submission time Handle Problem Language Result Execution time Memory
1041052 2024-08-01T14:22:40 Z mdn2002 Board Game (JOI24_boardgame) C++17
0 / 100
 4000 ms 1048576 KB 
/*
Mayoeba Yabureru
*/
#include<bits/stdc++.h>
using namespace std;
void solve() {
    int n, m, k;
    string s;
    cin >> n >> m >> k;
    vector gr(n + 1,vector<int>());
    vector<int> X(n + 1), type(n + 1);
    vector con(n + 2, vector<long long>(k + 2, 1e9));
    con[0].assign(k + 1, 0);
    for (int i = 1; i <= m; i ++) {
        int x, y;
        cin >> x >> y;
        gr[x].push_back(y);
        gr[y].push_back(x);
    }
    cin >> s;
    s.insert(s.begin(), '*');
    for (int i = 1; i <= k; i ++) cin >> X[i];
    for (int i = 1; i <= n; i ++) {
        if (s[i] == '0') continue;
        type[i] = 1;
        for (auto j : gr[i]) {
            if (s[j] == '1') type[i] = 2;
        }
    }
    for (int i = 2; i <= k; i ++) {
        vector dis(n + 1, vector<long long>(n + 1 ,1e9));
        queue<pair<int, int>> q;
        dis[X[i]][0] = 0;
        q.push({X[i], 0});

        while (q.size()) {
            auto [x, type] = q.front();
            q.pop();
            for (auto u : gr[x]) {
                if (s[u] == '0') {
                    if (dis[u][type] > dis[x][type] + 1) {
                        dis[u][type] = dis[x][type] + 1;
                        q.push({u, type});
                    }
                }
                else {
                    con[type + 1][i] = min(con[type + 1][i], dis[x][type] + 1);
                    if (type + 1 <= n && dis[u][type + 1] > dis[x][type] + 1) {
                        dis[u][type + 1] = dis[x][type] + 1;
                        q.push({u, type + 1});
                    }
                }
            }
        }
    }
    vector<long long> dis(n + 1, 1e18), ans(n + 1, 1e18);
    queue<int> q, nq;
    dis[X[1]] = 0;
    q.push(X[1]);

    int t = 0;
    while (t <= n) {
        long long add = 0;
        for (int i = 2; i <= k; i ++) {
            add += con[t][i];
        }
        while (q.size()) {
            int x = q.front();
            ans[x] = min(ans[x], dis[x] + add);
            q.pop();
            for (auto u : gr[x]) {
                if (dis[u] > dis[x] + 1) {
                    dis[u] = dis[x] + 1;
                    if (s[u] == '0') q.push(u);
                    else {
                        ans[u] = min(ans[u], dis[u] + add);
                        nq.push(u);
                    }
                }
            }
        }
        if (nq.size() == 0) break;
        q = nq;
        while (nq.size()) nq.pop();
        t ++;
    }

    for (int i = 1; i <= n; i ++) cout << ans[i] << endl;
}
/*
5 5 2
1 2
2 3
2 4
3 5
4 5
01000
1 5

8 7 5
1 3
5 7
4 6
2 6
2 3
7 8
1 5
10011010
4 6 4 7 1

12 13 3
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
1 10
2 9
7 12
11 12
110000011101
1 9 11

*/

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int T = 1;
    for (int I = 0; I < T; I ++){
        solve();
    }
}

Subtask #1
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4040 ms 142204 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4058 ms 142164 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4011 ms 142072 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 18268 KB Output is correct
2 Correct 1153 ms 71808 KB Output is correct
3 Execution timed out 4019 ms 80392 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 474 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 474 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 18268 KB Output is correct
2 Correct 1153 ms 71808 KB Output is correct
3 Execution timed out 4019 ms 80392 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #8
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4040 ms 142204 KB Time limit exceeded
2 Halted 0 ms 0 KB -