oj.uz

Submission #775499

# Submission time Handle Problem Language Result Execution time Memory
775499 2023-07-06T12:59:48 Z hgmhc None (JOI16_ho_t3) C++17
0 / 100
 57 ms 14696 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];
    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]>s[b]) swap(a,b);
        s[b]+=s[a],p[a]=b;
    }
    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];
int ans[Q];
disjoint_set<N> ds;
bool active[M], invalid[M];

void bfs_to_make_DAG() {
    bool vis[N]{}, vise[M]{};
    int dist[N];
    queue<int> q;
    q.push(1), dist[1] = 0, vis[1] = true;
    while (not empty(q)) {
        int s = q.front(); q.pop();
        vector<ii> el;
        for (auto [i,u] : adj[s]) {
            if (vis[u]) {
                if (dist[u] < dist[s]+1) {
                    if (not vise[i])
                        invalid[i] = true;
                        // dbg("%d (%d,%d)\n", i, s, u);
                }
                vise[i] = true;
                continue;
            }
            vis[u] = true;
            vise[i] = 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+N,1);
    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]];
            // dbg("enable edge (%d,%d)\n", u, v);
            if (not ds.same(u,v))
                ds.merge(u,v);
        }
    }
    
    rep(i,1,q) cout << ans[i] << '\n';
    // bfs 최단경로 DAG를 만들어 두면 되는 거 아닌가?
    // 사이클 존재 불가능. 왜냐하면 가중치가 1이기 때문에 한쪽 최단경로가 +a(>=1)인데 같아져야 함.
    // 오프라인 쿼리로 추가해나가면 좋을 듯.
    // 구현이 좀... 흠...
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4180 KB Output is correct
2 Incorrect 2 ms 4180 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4180 KB Output is correct
2 Incorrect 2 ms 4180 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 57 ms 14696 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4180 KB Output is correct
2 Incorrect 2 ms 4180 KB Output isn't correct
3 Halted 0 ms 0 KB -