Submission #1026581

#TimeUsernameProblemLanguageResultExecution timeMemory
1026581GrayMaking Friends on Joitter is Fun (JOI20_joitter2)C++17
0 / 100
1 ms348 KiB
// #pragma GCC optimize("O3") // #pragma GCC target("avx2") #include <algorithm> #include <climits> #include <ios> #include<iostream> #include <map> #include <queue> #include <set> #include <string> #include <vector> #define ll long long #define ff first #define ss second #define ull unsigned ll #define ln "\n" #define pll pair<ll, ll> #define INF 2e18 using namespace std; struct DSU{ vector<set<ll>> h_in, h_out, lead; vector<ll> par, sz; ll n, ecnt; DSU(ll N){ n=N; ecnt=0; par.resize(n+1, -1); h_in=h_out=lead = vector<set<ll>>(n+1); for (ll i=1; i<=n; i++) lead[i].insert(i); sz.resize(n+1, 1); } void debug(){ return; for (ll i=1; i<=n; i++){ cout << i << "::\n"; cout << "lead: "; for (auto ch:lead[i]) cout << ch << ' '; cout << "\nin: "; for (auto ch:h_in[i]) cout << ch << ' '; cout << "\nout: "; for (auto ch:h_out[i]) cout << ch << ' '; cout << ln << ln; } } queue<pair<ll, ll>> unity; ll get(ll u){ return par[u]==-1?u:par[u]=get(par[u]); } void elink(ll u, ll v, int add=1){ ll pu = get(u), pv=get(v); // cout << "Request: " << u << "->" << v << " - " << pu << " -> " << pv << ln; if (pu==pv or h_in[pv].count(pu)){ // if (add==0) cout << "Spec: " << u << " " << v << ln; return; }else if (h_out[pv].count(pu)){ h_in[pv].insert(pu); h_out[pu].insert(pv); unity.push({pu, pv}); }else{ ecnt+=sz[v]*add; h_in[pv].insert(pu); h_out[pu].insert(pv); lead[pv].insert(u); } } void link(ll u, ll v){ elink(u, v); proc_unities(); debug(); } void unite(ll u, ll v){ u=get(u); v=get(v); if (u==v) return; if (h_in[u].size()+h_out[u].size()+lead[u].size()<h_in[v].size()+h_out[v].size()+lead[v].size()) swap(u, v); par[v]=u; // cout << "PDEB: " << ecnt << ":" << sz[u] << ' ' << sz[v] << ln; ecnt+=sz[u]*lead[v].size()+sz[v]*lead[u].size(); sz[u]+=sz[v]; // cout << "Unite: " << v << "->" << u << ln; // cout << "PDEB: " << ecnt << ln; for (auto mem:lead[v]){ ecnt-=sz[u]*lead[u].count(mem); lead[u].insert(mem); } lead[v].clear(); h_in[v].erase(u); h_out[u].erase(v); h_in[u].erase(v); h_out[v].erase(u); for (auto mem:h_in[v]){ h_out[mem].erase(v); elink(mem, u, 0); } h_in[v].clear(); for (auto mem:h_out[v]){ h_in[mem].erase(v); elink(u, mem, 0); } h_out[v].clear(); } void proc_unities(){ while (!unity.empty()){ auto cur = unity.front(); unity.pop(); unite(cur.ff, cur.ss); } } }; void solve(){ ll n, m; cin >> n >> m; DSU tr(n); for (ll i=0; i<m; i++){ ll u, v; cin >> u >> v; tr.link(u, v); cout << tr.ecnt << ln; } } int main(){ ios_base::sync_with_stdio(0); cin.tie(nullptr); ll t=1; // cin >> t; while (t--) { solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...