Submission #502299

#	Time	Username	Problem	Language	Result	Execution time	Memory
502299		benedict0724	철도 요금 (JOI16_ho_t3)	C++17	100 / 100	147 ms	18592 KiB

2016_ho_t3

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int INF = 1e8;

int u[200002], v[200002], ans[200002], dist[100002], R[200002], nes[200002], use[100002];
vector<pair<int, int>> adj[100002];

int main()
{
    ios::sync_with_stdio(false); cin.tie(NULL);
    int N, M, Q; cin >> N >> M >> Q;
    for(int i=1;i<=M;i++)
    {
        cin >> u[i] >> v[i];
        adj[u[i]].push_back({v[i], i});
        adj[v[i]].push_back({u[i], i});
    }

    for(int i=1;i<=Q;i++) cin >> R[i];

    for(int i=2;i<=N;i++) dist[i] = INF;
    queue<int> q;
    q.push(1);
    while(!q.empty())
    {
        int now = q.front(); q.pop();
        for(auto uv : adj[now])
        {
            int i = uv.first;
            if(dist[i] > dist[now] + 1)
            {
                dist[i] = dist[now] + 1;
                q.push(i);
            }
        }
    }

    for(int i=1;i<=M;i++)
    {
        if(dist[u[i]] != dist[v[i]]) nes[i] = 1;
    }

    for(int i=1;i<=Q;i++) nes[R[i]] = 0;

    q.push(1);
    int tmp = 0;
    use[1] = 1;
    while(!q.empty())
    {
        int now = q.front(); q.pop();
        tmp++;
        for(auto uv : adj[now])
        {
            if(!nes[uv.second]) continue;
            int i = uv.first;
            if(dist[i] == dist[now] + 1 && !use[i])
            {
                q.push(i);
                use[i] = 1;
            }
        }
    }

    for(int i=Q;i>=1;i--)
    {
        ans[i] = N - tmp;
        if(dist[u[R[i]]] == dist[v[R[i]]]) continue;
        nes[R[i]] = 1;
        int A, B;
        if(dist[u[R[i]]] > dist[v[R[i]]])
        {
            A = v[R[i]];
            B = u[R[i]];
        }
        else
        {
            A = u[R[i]];
            B = v[R[i]];
        }

        if(use[A] && !use[B])
        {
            q.push(B);
            use[B] = 1;
            while(!q.empty())
            {
                int now = q.front(); q.pop();
                tmp++;
                for(auto uv: adj[now])
                {
                    if(!nes[uv.second]) continue;
                    int j = uv.first;
                    if(dist[j] == dist[now]+1 && !use[j])
                    {
                        q.push(j);
                        use[j] = 1;
                    }
                }
            }
        }
    }

    for(int i=1;i<=Q;i++) cout << ans[i] << "\n";
}

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