제출 #1206004

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1206004		agrim_09	철도 요금 (JOI16_ho_t3)	C++20	100 / 100	250 ms	24164 KiB

2016_ho_t3

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template <class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define endl '\n';
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
#define py cout << "YES" << endl;
#define pn cout << "NO" << endl;
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define int long long
typedef long long ll;
typedef unsigned long long ull;
const ll inf = 1e18;
const ll mod = 1e9+7;


// #ifndef ONLINE_JUDGE
// #include "algo/Standard_Stuff/debug.cpp"
// #else
// #define debug(...) 42
// #endif

// void judge(){
//     srand(time(NULL));
//     #ifndef ONLINE_JUDGE
//     freopen("1.txt","r",stdin);
//     freopen("2.txt","w",stdout);
//     #endif
// }

struct ufds{
    vector<int>par;
    vector<int>sz;
    ufds(int n){
        par.resize(n);
        sz.resize(n);
        for(int i = 0;i<n;i++){
            par[i] = i; sz[i] = 1;
        }
    }
    int get(int u){
        if(u==par[u]) return u;
        return par[u] = get(par[u]);
    }
    void unite(int u, int v){
        //u--; v--;
        u = get(u); v = get(v);
        if(u!=v){
            if(sz[u]>sz[v]){
                swap(u,v);
            }
            par[u] = v;
            sz[v] += sz[u];
        }
    }
    bool same_comp(int u, int v){
        return (get(u)==get(v));
    }
};

// Look for edge cases!!!
signed main(){
    //judge();
    int n,m,q; cin >> n >> m >> q;
    vector<vector<int>>adj(n);
    vector<pair<int, int>>roads;
    for(int i = 0,u,v;i<m;i++){
        cin >> u >> v; u--; v--;
        adj[u].pb(v); adj[v].pb(u);
        roads.pb({u,v});
    }
    vector<int>dist(n,inf);
    queue<int>qu; qu.push(0);
    dist[0] = 0;

    //debug(adj[1]);

    while(qu.size()){
        int node = qu.front();
        qu.pop();
        for(auto child : adj[node]){
            if(dist[child]>dist[node]+1){
                dist[child] = dist[node] + 1;
                qu.push(child);
            }
        }
    }

    ufds p(n);
    vector<bool>connected_to_1(n,false);
    connected_to_1[0] = true;

    vector<vector<int>>adj2(n);

    auto dfs_add = [&](auto&&self, int u)-> void{
        for(auto v : adj2[u]){
            p.unite(u,v);
            self(self,v);
        }
        connected_to_1[u] = true;
        adj2[u].clear();
    };

    auto join = [&](int u, int v){
        if(dist[u]==dist[v]){
            return;
        }
        if(dist[u]>dist[v]){
            swap(u,v);
        }
        if(connected_to_1[u]){
            p.unite(u,v);
            dfs_add(dfs_add,v);
        }
        else{
            adj2[u].pb(v);
        }
    };


    vector<int>queries(q);
    vector<bool>road(m,true);
    for(auto &x : queries){
        cin >> x; x--; road[x] = false;
    }
    for(int i = 0;i<m;i++){
        if(road[i]){
            if(dist[roads[i].first]==dist[roads[i].second]){
                continue;
            }
            if(dist[roads[i].first]>dist[roads[i].second]){
                swap(roads[i].first,roads[i].second);
            }
            join(roads[i].first,roads[i].second);
            if(connected_to_1[roads[i].first]){
                connected_to_1[roads[i].second] = true;
            }
        }
    }
    //debug(dist);
    //debug(connected_to_1);
    vector<int>ans;
    for(int i = q-1;i>=0;i--){
        ans.pb(p.sz[p.get(0)]);
        if(dist[roads[queries[i]].first]==dist[roads[queries[i]].second]){
            continue;
        }
        join(roads[queries[i]].first,roads[queries[i]].second);
        //debug(connected_to_1);
    }

    reverse(ans.begin(),ans.end());
    for(auto x : ans){
        cout << n-x << endl;
    }
}

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