Submission #503663

#	Time	Username	Problem	Language	Result	Execution time	Memory
503663		jk410	철도 요금 (JOI16_ho_t3)	C++17	100 / 100	153 ms	15968 KiB

2016_ho_t3

#include <bits/stdc++.h>
using namespace std;
const int INF=1e9;
struct nosun{
    int from,to;
};
struct edge{
    int v,idx;
};
int N,M,Q,Ans;
nosun Nosun[200001];
vector<edge> Edge[100001];
int Dist[100001];
queue<int> Queue;
int Cnt[100001];
bool Visited[200001];
bool f(int idx){
    return (Dist[Nosun[idx].from]==Dist[Nosun[idx].to]);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>N>>M>>Q;
    for (int i=1; i<=N; i++)
        Dist[i]=INF;
    for (int i=1; i<=M; i++){
        cin>>Nosun[i].from>>Nosun[i].to;
        Edge[Nosun[i].from].push_back({Nosun[i].to,i});
        Edge[Nosun[i].to].push_back({Nosun[i].from,i});
    }
    Dist[1]=0;
    Queue.push(1);
    while (!Queue.empty()){
        int t=Queue.front();
        Queue.pop();
        for (edge i:Edge[t]){
            if (Dist[i.v]>Dist[t]+1){
                Dist[i.v]=Dist[t]+1;
                Queue.push(i.v);
            }
        }
    }
    for (int i=1; i<=M; i++){
        if (f(i))
            continue;
        if (Dist[Nosun[i].from]>Dist[Nosun[i].to])
            swap(Nosun[i].from,Nosun[i].to);
        Cnt[Nosun[i].to]++;
    }
    while (Q--){
        int r;
        cin>>r;
        if (!f(r)&&!Visited[r])
            Queue.push(r);
        while (!Queue.empty()){
            int t=Queue.front();
            Queue.pop();
            Visited[t]=true;
            if (--Cnt[Nosun[t].to]==0){
                Ans++;
                for (edge i:Edge[Nosun[t].to]){
                    if (f(i.idx)||Visited[i.idx])
                        continue;
                    Queue.push(i.idx);
                }
            }
        }
        cout<<Ans<<"\n";
    }
    return 0;
}

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