oj.uz

답안 #775542

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
775542 2023-07-06T13:45:34 Z hgmhc 철도 요금 (JOI16_ho_t3) C++17
0 / 100
 66 ms 16976 KB 
#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]));
        p[a]=b;
    }
    void lazy_push(int x, int y) {
        lazy[find(x)].push_back(y);
    }
    void lazy_pop(int x) {
        x = find(x);
        for (auto y : lazy[x]) {
            if (not same(x,y)) merge(x,y);
        }
    }
    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);
        }
    }
    vector<int> lazy[N];
    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,v)) {
                    ds.lazy_push(u,v);
                } else {
                    ds.merge(u,v);
                    ds.lazy_pop(v);
                }
            }
            // dbg("(%d,%d)\n", u,v);
        }
    }
    
    rep(i,1,q) cout << ans[i] << '\n';
}

Subtask #1
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 8404 KB Output is correct
2 Incorrect 4 ms 8404 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 8404 KB Output is correct
2 Incorrect 4 ms 8404 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 66 ms 16976 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 8404 KB Output is correct
2 Incorrect 4 ms 8404 KB Output isn't correct
3 Halted 0 ms 0 KB -