Submission #1225567

#TimeUsernameProblemLanguageResultExecution timeMemory
1225567GrayMaking Friends on Joitter is Fun (JOI20_joitter2)C++17
0 / 100
0 ms320 KiB
#include <algorithm> #include <bits/stdc++.h> #include <cassert> #define ll long long #define ff first #define ss second #define ln "\n" const ll INF = 2e18; const ll MOD = 1e9+7; using namespace std; struct DSU{ vector<ll> p; vector<set<ll>> nodes; vector<set<ll>> in, outp; queue<pair<ll, ll>> buffer; ll n, cnt; DSU(ll N){ n=N; p.resize(N+1, -1); cnt=0; nodes.resize(n+1); for (ll i=1; i<=n; i++) nodes[i].insert(i); in.resize(n+1); outp.resize(n+1); } ll get(ll x){ return p[x]==-1?x:p[x]=get(p[x]); } void unite(ll u, ll v){ if (in[u].size()+nodes[u].size()<in[v].size()+nodes[v].size()) swap(u, v); p[v]=u; vector<ll> ers; // cout << u << " & " << v << ln; // cout << nodes[u].size() << " and " << nodes[v].size() << ln; // cout << "From: " << cnt << ln; for (auto cv:in[v]){ if(get(cv)==u){ cnt-=nodes[v].size(); ers.push_back(cv); } } for (auto cv:ers){ in[v].erase(cv); } for (auto cv:nodes[v]){ if (in[u].count(cv)){ cnt-=nodes[u].size(); } in[u].erase(cv); } outp[u].erase(v); outp[v].erase(u); // cout << "Mid: " << cnt << ln; cnt+=in[u].size()*nodes[v].size()+in[v].size()*nodes[u].size(); cnt+=nodes[u].size()*nodes[v].size()*2; for (auto cv:in[v]){ if (in[u].count(cv)) cnt-=nodes[u].size()+nodes[v].size(); outp[get(cv)].erase(v); in[u].insert(cv); outp[get(cv)].insert(u); // cout << u << ": "; // for (auto ch:outp[u]) cout << ch << " "; // cout << " || "; // cout << get(cv) << "<-" << cv << " so " << outp[u].count(get(cv)) << ln; if (outp[u].count(get(cv))) buffer.push({u, cv}); } for (auto cv:nodes[v]) nodes[u].insert(cv); // cout << "To: " << cnt << ln; nodes[v].clear(); in[v].clear(); outp[v].clear(); } void link(ll u, ll v){ buffer.push({u, v}); while (!buffer.empty()){ tie(u, v) = buffer.front(); ll pu = get(u), pv=get(v); buffer.pop(); if (pu==pv or (in[pv].count(u) and !outp[pv].count(pu))) continue; else if (outp[pv].count(pu)){ unite(pu, pv); }else{ cnt+=nodes[pv].size(); outp[pu].insert(pv); in[pv].insert(u); } // cout << u << " -> " << v << ": " << cnt << ln; } } }; 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.cnt << ln; } } int main() { ios_base::sync_with_stdio(false); 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...