제출 #502283

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
502283		benedict0724	철도 요금 (JOI16_ho_t3)	C++17	0 / 100	80 ms	12828 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], path[100002], siz[200002];
vector<int> adj[100002];

int f(int x)
{
    if(x == path[x]) return x;
    return path[x] = f(path[x]);
}

void uni(int x, int y)
{
    x = f(x); y = f(y);
    if(x == y) return;
    path[x] = y;
    siz[y] += siz[x];
}

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]);
        adj[v[i]].push_back(u[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(int i : adj[now])
        {
            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;
    for(int i=1;i<=N;i++)
    {
        path[i] = i;
        siz[i] = 1;
    }

    for(int i=1;i<=M;i++)
    {
        if(nes[i])
        {
            uni(u[i], v[i]);
        }
    }
    for(int i=Q;i>=1;i--)
    {
        ans[i] = N - siz[f(1)];
        if(dist[u[R[i]]] != dist[v[R[i]]]) uni(u[R[i]], v[R[i]]);
    }

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

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