Submission #1157548

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157548		mocha	철도 요금 (JOI16_ho_t3)	C++20	100 / 100	189 ms	29660 KiB

2016_ho_t3

#include <bits/stdc++.h>
using namespace std;
const int mx = 2e5+5;
const int inf = 1e9+5;

int n, m, q;
vector<int> g[mx], ng[mx], rg[mx];
pair<int, int> e[mx];
int qs[mx];
int dis[mx];
int ans[mx];
int dp[mx<<1];

signed main() {
    cin >> n >> m >> q;
    for (int i=1;i<=m;i++) {
        int u, v;
        cin >> u >> v;
        e[i] = {u, v};
        g[u].push_back(i);
        g[v].push_back(i);
    }
    for (int i=1;i<=n;i++) dis[i] = inf;
    queue<int> que;
    dis[1] = 0;
    que.push(1);
    while (que.size()) {
        int x = que.front(); que.pop();
        for (int i:g[x]) {
            auto [u, v] = e[i];
            if (u != x) swap(u, v);
            if (dis[v] == inf) {
                dis[v] = dis[u] + 1;
                que.push(v);
            }
        }
    }
    for (int i=1;i<=n;i++) {
        for (int j:g[i]) {
            auto [u, v] = e[j];
            if (u != i) swap(u, v);
            if (dis[v] == dis[u] + 1) {
                ng[i].push_back(j);
                rg[v].push_back(j);
            }
        }
    }
    for (int i=1;i<=m;i++) dp[i+n] = inf;
    for (int i=1;i<=q;i++) {
        int x;
        cin >> x;
        dp[x + n] = i;
    }
    vector<int> ve;
    for (int i=1;i<=n;i++) ve.push_back(i);
    sort(ve.begin(), ve.end(), [&](int a, int b) {
         return dis[a] < dis[b];
    });
    dp[1] = q+1;
    for (int i:ve) {
        if (i == 1) continue;
        dp[i] = 0;
        for (int j:rg[i]) {
            auto [u, v] = e[j];
            if (u != i) swap(u, v);
            dp[i] = max(dp[i], min(dp[v], dp[j+n]));
        }
        ans[dp[i]]++;
    }
    for (int i=1;i<=q;i++) {
        ans[i] = ans[i-1] + ans[i];
        cout << ans[i] << "\n";
    }
}

• Subtask 1: 12 / 12
• Subtask 2: 14 / 14
• Subtask 3: 35 / 35
• Subtask 4: 39 / 39