Submission #545447

#	Time	Username	Problem	Language	Result	Execution time	Memory
545447		pokmui9909	철도 요금 (JOI16_ho_t3)	C++17	100 / 100	198 ms	26624 KiB

2016_ho_t3

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define x first
#define y second
ll N, M, K;
pair<ll, ll> E[200005];
vector<pair<ll, ll>> G[200005];
ll dist[200005];
const ll INF = 1e18;
ll deg[200005];
ll chk[200005];

int main(){
    cin.tie(0) -> sync_with_stdio(false);

    cin >> N >> M >> K;
    for(int i = 1; i <= M; i++){
        cin >> E[i].x >> E[i].y;
        G[E[i].x].push_back({E[i].y, i});
        G[E[i].y].push_back({E[i].x, i});
    }
    queue<ll> Q;
    fill(dist, dist + N + 1, INF);
    Q.push(1); dist[1] = 0;
    while(!Q.empty()){
        ll u = Q.front(); Q.pop();
        for(auto i : G[u]){
            if(dist[i.x] <= dist[u] + 1) continue;
            dist[i.x] = dist[u] + 1;
            Q.push(i.x);
        }
    }
    for(int i = 1; i <= M; i++){
        if(dist[E[i].x] == dist[E[i].y]) continue;
        if(dist[E[i].x] > dist[E[i].y]) swap(E[i].x, E[i].y);
        deg[E[i].y]++;
    }
    ll r = 0;
    while(K--){
        ll t; cin >> t;
        if(!chk[t] && dist[E[t].x] != dist[E[t].y]){
            Q.push(t); chk[t] = 1;
            while(!Q.empty()){
                ll u = Q.front(); Q.pop();
                deg[E[u].y]--;
                if(deg[E[u].y] == 0){
                    r++;
                    for(auto i : G[E[u].y]){
                        if(chk[i.y] || dist[E[i.y].x] == dist[E[i.y].y]) continue;
                        chk[i.y] = 1;
                        Q.push(i.y);
                    }
                }
            }
        }
        cout << r << '\n';
    }
}

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