Submission #67280511

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#include "../../Templates/C++/debug.h"
#else
#define debug(...) 42
#endif

typedef long long ll;
typedef long double ld;
 
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
 
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;

template<class T> using pq = priority_queue<T>;
template<class T> using pqg = priority_queue<T, vector<T>, greater<T>>;

#define mp make_pair
#define pb push_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define ins insert
#define lso(s) ((s) & -(s))
int lg(ll s) { return s ? __builtin_clzll(1) - __builtin_clzll(s) : -1; }//lg(1)=0, lg(2)=1, lg(3)=1, lg(4)=2, ...
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

const int MOD = 998244353;
const double EPS = 1e-9;
const char nl = '\n';
const int INF = 1e9;
const ll INFL = 4e18;
ll gcd(ll a,ll b) { if (b==0) return a; return gcd(b, a%b); }
ll lcm(ll a,ll b) { return a/gcd(a,b)*b; }
ll floor(ll a, ll b) { return a / b - (a % b < 0); }
ll ceil(ll a, ll b) { return a / b + (a % b > 0); }

template<typename T>
istream& operator>>(istream& in, vector<T> &vec){
    for(auto &x : vec){
        in>>x;
    }
    return in;
}

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll gen() {
	ll x = 0;
	while(x == 0)
		x = rng() % MOD;
	return x;
}

struct mint {
  ll x;
  mint(ll x=0):x((x%MOD+MOD)%MOD){}
  mint& operator+=(const mint a) {if ((x += a.x) >= MOD) x -= MOD;return *this;}
  mint& operator-=(const mint a) {if ((x += MOD-a.x) >= MOD) x -= MOD;return *this;}
  mint& operator*=(const mint a) {(x *= a.x) %= MOD;return *this;}
  mint operator+(const mint a) const {mint res(*this);return res+=a;}
  mint operator-(const mint a) const {mint res(*this);return res-=a;}
  mint operator*(const mint a) const {mint res(*this);return res*=a;}
  mint pow(ll b) const {
    mint res(1), a(*this);
    while (b) {
      if (b & 1) res *= a;
      a *= a;
      b >>= 1;
    }
    return res;
  }
  // for prime MOD
  mint inv() const {return pow(MOD-2);}
  mint& operator/=(const mint a) {return (*this) *= a.inv();}
  mint operator/(const mint a) const {mint res(*this);return res/=a;}
};
ostream& operator<<(ostream& os, const mint& a) {os << a.x; return os;}

struct UF {
	vi e;
	UF(int n) : e(n, -1) {}
	bool sameSet(int a, int b) { return find(a) == find(b); }
	int size(int x) { return -e[find(x)]; }
	int find(int x) { return e[x] < 0 ? x : e[x] = find(e[x]); }
	bool join(int a, int b) {
		a = find(a), b = find(b);
		if (a == b) return false;
		// if (e[a] > e[b]) swap(a, b);
		e[a] += e[b]; e[b] = a;
		return true;
	}
};

void solve() {
    int N; cin >> N;
    int M; cin >> M;
    vector<set<int>> al(N);
    vector<array<int, 2>> el(M);
    for(auto&[u, v] : el) {
        cin >> u >> v; u--, v--;
        al[u].ins(v);
        al[v].ins(u);
    }
    int cur = M;
    UF uf(N);
    int Q; cin >> Q;
    for(int i = 0; i < Q; i++) {
        int id; cin >> id; id--;
        auto[u, v] = el[id];
        if(uf.sameSet(u, v)) {
            cout << cur << nl;
            continue;
        }
        u = uf.find(u);
        v = uf.find(v);
        if(!al[u].count(v)) {
            cout << cur << nl;
            continue;
        }
        if(sz(al[u]) < sz(al[v])) swap(u, v);
        al[u].erase(v);
        al[v].erase(u);
        cur--;
        vector<array<int, 2>> rem;
        for(int w : al[v]) {
            if(al[u].count(w)) {
                rem.pb({v, w});
            } else {
                al[u].ins(w);
                al[w].ins(u);
                al[w].erase(v);
            }
        }
        cur -= sz(rem);
        for(auto[x, y] : rem) {
            al[x].erase(y);
            al[y].erase(x);
        }
        cout << cur << nl;
        uf.join(u, v);
        // debug(al);
    }

}


int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin.exceptions(cin.failbit);
    int T = 1;
    // cin >> T;
    while(T--) {
        solve();
    }
	return 0;
}

Submission Info

Judge Result