Submission #503644

#	Time	Username	Problem	Language	Result	Execution time	Memory
503644		jk410	철도 요금 (JOI16_ho_t3)	C++17	61 / 100	2561 ms	15856 KiB

2016_ho_t3

#include <bits/stdc++.h>
using namespace std;
const int INF=1e9;
struct nosun{
    int u,v;
};
struct edge{
    int v,cost;
    bool operator<(const edge &tmp)const{
        return cost>tmp.cost;
    }
};
int N,M,Q;
nosun Nosun[200001];
int R[200001];
bool Used[200001];
vector<int> Edge[100001];
int D[100001];
int Dist[100001];
priority_queue<edge> PQ;
int Ans[200001];
void dijkstra(int t){
    while (!PQ.empty()){
        edge tmp=PQ.top();
        PQ.pop();
        if (Dist[tmp.v]<tmp.cost)
            continue;
        for (int i:Edge[tmp.v]){
            if (Dist[i]>tmp.cost+1){
                D[i]=t;
                Dist[i]=tmp.cost+1;
                PQ.push({i,Dist[i]});
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>N>>M>>Q;
    for (int i=1; i<=N; i++){
        D[i]=Q+1;
        Dist[i]=INF;
    }
    for (int i=1; i<=M; i++)
        cin>>Nosun[i].u>>Nosun[i].v;
    for (int i=1; i<=Q; i++){
        cin>>R[i];
        Used[R[i]]=true;
    }
    for (int i =1; i<=M; i++){
        if (Used[i])
            continue;
        Edge[Nosun[i].u].push_back(Nosun[i].v);
        Edge[Nosun[i].v].push_back(Nosun[i].u);
    }
    Dist[1]=0;
    PQ.push({1,0});
    dijkstra(Q+1);
    for (int i=Q; i; i--){
        Edge[Nosun[R[i]].u].push_back(Nosun[R[i]].v);
        Edge[Nosun[R[i]].v].push_back(Nosun[R[i]].u);
        int v;
        if (Dist[Nosun[R[i]].u]>Dist[Nosun[R[i]].v])
            v=Nosun[R[i]].v;
        else
            v=Nosun[R[i]].u;
        PQ.push({v,Dist[v]});
        dijkstra(i);
    }
    for (int i=1; i<=N; i++){
        if (D[i]==Q+1)
            continue;
        Ans[D[i]]++;
    }
    for (int i=1; i<=Q; i++){
        Ans[i]+=Ans[i-1];
        cout<<Ans[i]<<"\n";
    }
    return 0;
}

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