Submission #775589

#	Time	Username	Problem	Language	Result	Execution time	Memory
775589		hgmhc	철도 요금 (JOI16_ho_t3)	C++17	100 / 100	89 ms	18508 KiB

2016_ho_t3

#include <bits/stdc++.h>
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define per(i,a,b) for (auto i = (b); i >= (a); --i)
#define all(x) begin(x),end(x)
#define siz(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)
#define dbg(...) fprintf(stderr,__VA_ARGS__)
#define fi first
#define se second
using namespace std; using ll = long long; using ii = pair<int,int>;

const int N = 1e5+3, M = 2e5+3, Q = M;
int n, m, q;
ii edge[M];
vector<ii> adj[N];
int r[Q], ans[Q];
int dist[N], deltime[M];
int ind[N];

void bfs_to_make_DAG() {
    bool vis[N]{};
    queue<int> q;
    q.push(1), dist[1] = 0, vis[1] = true;
    while (not empty(q)) {
        int s = q.front(); q.pop();
        for (auto [i,u] : adj[s]) {
            if (vis[u]) continue;
            vis[u] = true;
            dist[u]=dist[s]+1;
            q.push(u);
        }
    }
}

void topology_dp() {
    queue<int> q;
    q.push(1), deltime[1] = ::q+1;
    while (not empty(q)) {
        int s = q.front(); q.pop();
        for (auto [u,w] : adj[s]) {
            Mup(deltime[u], min(deltime[s],w));
            if (--ind[u] == 0) q.push(u);
        }
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m >> q;
    rep(i,1,m) {
        cin >> edge[i].fi >> edge[i].se;
        adj[edge[i].fi].push_back({i,edge[i].se});
        adj[edge[i].se].push_back({i,edge[i].fi});
    }
    bfs_to_make_DAG();
    fill(deltime,deltime+M,1e9);
    rep(i,1,q) {
        cin >> r[i];
        deltime[r[i]] = i;
    }
    rep(i,1,n) adj[i].clear();
    
    rep(i,1,m) {
        auto &[u,v] = edge[i];
        if (dist[u]>dist[v]) swap(u,v);
        if (dist[v]-dist[u]==1) {
            adj[u].push_back({v,deltime[i]});
            ind[v]++;
        }
    }
    fill(deltime,deltime+M,-1);
    topology_dp();
    rep(i,1,n) ans[deltime[i]]++;
    rep(i,1,q) cout << (ans[i]+=ans[i-1]) << '\n';
}

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