Submission #775577

#	Time	Username	Problem	Language	Result	Execution time	Memory
775577		hgmhc	철도 요금 (JOI16_ho_t3)	C++17	0 / 100	65 ms	14584 KiB

2016_ho_t3

#include <bits/stdc++.h>
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define per(i,a,b) for (auto i = (b); i >= (a); --i)
#define all(x) begin(x),end(x)
#define siz(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)
#define dbg(...) fprintf(stderr,__VA_ARGS__)
#define fi first
#define se second
using namespace std; using ll = long long; using ii = pair<int,int>;

template <const int N>
struct disjoint_set {
    int p[N], s[N];
    vector<int> lazy[N];
    disjoint_set(){ fill(s,s+N,1), iota(p,p+N,0); }
    int find(int x) {
        if (x == p[x]) return x;
        return p[x] = find(p[x]);
    }
    bool same(int a, int b){ return find(a)==find(b); }
    void merge(int a, int b) {
        a = find(a), b = find(b);
        assert(a!=b);
        if (s[a]+siz(lazy[a])>s[b]+siz(lazy[b])) swap(a,b);
        s[b]+=s[a];
        lazy[b].insert(end(lazy[b]),all(lazy[a]));
        lazy[a].clear();
        p[a]=b;
    }
    void lazy_push(int x, int y) {
        lazy[find(x)].push_back(y);
    }
    void lazy_pop(int x) {
        x = find(x);
        while (not empty(lazy[x])) {
            vector<int> lazy_here;
            for (auto y : lazy[x]) {
                y = find(y);
                if (not same(x,y)) {
                    lazy_here.insert(end(lazy_here),all(lazy[y]));
                    lazy[y].clear();
                }
            }
            for (auto y : lazy[x]) if (not same(x,y)) merge(x,y);
            lazy[x].clear();
            x = find(x);
            lazy[x] = lazy_here;
        }
    }
    int size(int x){ return s[find(x)]; }
};

const int N = 1e5+3, M = 2e5+3, Q = M;
int n, m, q;
ii edge[M];
vector<ii> adj[N];
int r[Q], ans[Q];
disjoint_set<N> ds;
bool active[M], invalid[M];
int dist[N];

void bfs_to_make_DAG() {
    bool vis[N]{};
    queue<int> q;
    q.push(1), dist[1] = 0, vis[1] = true;
    while (not empty(q)) {
        int s = q.front(); q.pop();
        for (auto [i,u] : adj[s]) {
            if (vis[u]) {
                if (abs(dist[u]-dist[s])!=1) {
                    invalid[i] = true;
                }
                continue;
            }
            vis[u] = true;
            dist[u]=dist[s]+1;
            q.push(u);
        }
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m >> q;
    rep(i,1,m) {
        cin >> edge[i].fi >> edge[i].se;
        adj[edge[i].fi].push_back({i,edge[i].se});
        adj[edge[i].se].push_back({i,edge[i].fi});
    }
    bfs_to_make_DAG();
    fill(active,active+M,true);
    rep(i,1,q) cin >> r[i], active[r[i]] = false;
    
    rep(i,1,m) {
        if (active[i] and not invalid[i]) {
            auto [u,v] = edge[i];
            if (not ds.same(u,v))
                ds.merge(u,v);
        }
    }
    per(i,1,q) {
        // rep(j,1,n) if (ds.same(1,j)) dbg("%d ", j);
        // dbg("\n");
        ans[i] = n-ds.size(1);
        if (i > 1 and not invalid[r[i]]) {
            auto [u,v] = edge[r[i]];
            if (not ds.same(u,v)) {
                if (dist[u]>dist[v]) swap(u,v);
                if (ds.same(1,u)) {
                    if (not ds.same(u,v)) ds.merge(u,v);
                } else {
                    ds.lazy_push(u,v);
                }
            }
            ds.lazy_pop(1);
            // dbg("(%d,%d)\n", u,v);
        }
    }
    rep(i,1,q) cout << ans[i] << '\n';
}

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