Submission #1316873

#TimeUsernameProblemLanguageResultExecution timeMemory
1316873LIABoard Game (JOI24_boardgame)C++17
3 / 100
4094 ms6416 KiB
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define v vector
#define lp(i, s, e) for (ll i = s; i < e; ++i)
#define pll pair<ll, ll>

ll n, m, k;
v<v<ll>> g;
v<ll> loc;
v<ll> s;
ll stop_cnt = 0;

void bfs(ll node, v<ll> &dist, v<ll> &touch) {
    dist[node] = 0;
    queue<ll> q;
    q.push(node);
    while (!q.empty()) {
        auto nd = q.front();
        ll dis = dist[nd];
        q.pop();
        for (auto it : g[nd]) {
            if (dist[it] > dis + 1) {
                dist[it] = dis + 1;
                touch[it] = touch[nd];
                if (s[it] == 1)
                    touch[it] = 1;
                q.push(it);
            } else if (dist[it] == dis + 1 && touch[it] == 1 && touch[nd] == 0) {
                touch[it] = 0;
                q.push(it);
            }
        }
    }
}

void bfs2(ll node, v<ll> &dist) {
    dist[node] = 0;
    queue<ll> q;
    q.push(node);
    while (!q.empty()) {
        auto nd = q.front();
        if (s[nd] == 1)
            continue;
        ll dis = dist[nd];
        q.pop();
        for (auto it : g[nd]) {
            if (dist[it] > dis + 1) {
                dist[it] = dis + 1;
                q.push(it);
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> k;
    g.resize(n);
    loc.resize(k);
    s.resize(n);
    lp(i, 0, m) {
        ll a, b;
        cin >> a >> b;
        a--;
        b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    string s1;
    cin >> s1;
    ll point = 0;
    lp(i, 0, n) {
        s[i] = (s1[i] == '1');
        if (s[i] == 1) {
            stop_cnt++;
            point = i;
        }
    }

    lp(i, 0, k) {
        cin >> loc[i];
        loc[i]--;
    }

    v<ll> dis(n, 1e18), touch(n, 0), nn(n, 0);

    bfs(loc[0], dis, touch);
    
    v<ll> dis_from_stp(n, 1e18);
    bfs(point, dis_from_stp, nn);

    v<ll> dis3(n, 1e18);

    bfs2(loc[0], dis3);
    ll sumi = 0;
    lp(i, 1, k) { sumi += dis_from_stp[loc[i]]; }
    lp(i, 0, n) {
        ll ans = 1e18;
        if (touch[i]) {
            ans = dis[i] + sumi;
        } else {
            ans = dis[i]; 
        }
        ans = min(ans, dis3[i]);
        cout << ans << '\n';
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...