Submission #1041032

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041032		mdn2002	Board Game (JOI24_boardgame)	C++17	0 / 100	4046 ms	1048576 KiB

Main

/*
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<long long> dis(n + 1, 1e9);
        queue<pair<int, int>> q;
        vector<pair<int, long long>> nq;
        dis[X[i]] = 0;
        q.push({X[i], 0});

        int t = 0;
        while (t + 1 <= n) {
            while (q.size()) {
                auto [x, type] = q.front();
                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, 1});
                        else {
                            con[t + 1][i] = min(con[t + 1][i], dis[u]);
                            nq.push_back({u, dis[u]});
                        }
                    }
                }
                if (type == 0) dis[x] = 1e9;
            }
            if (nq.size() == 0) break;
            dis.assign(n + 1, 1e9);
            for (auto [x, y] : nq) {
                q.push({x, 0});
                dis[x] = min(dis[x], y);
            }
            nq.clear();
            t ++;
        }
    }
    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 / 3
• Subtask 2: 0 / 7
• Subtask 3: 0 / 7
• Subtask 4: 0 / 19
• Subtask 5: 0 / 23
• Subtask 6: 0 / 9
• Subtask 7: 0 / 23
• Subtask 8: 0 / 9