Submission #1074812

#TimeUsernameProblemLanguageResultExecution timeMemory
1074812underwaterkillerwhaleMaking Friends on Joitter is Fun (JOI20_joitter2)C++17
100 / 100
1974 ms127756 KiB
#include <bits/stdc++.h> #define ll long long #define rep(i,m,n) for(int i=(m); i<=(n); i++) #define reb(i,m,n) for(int i=(m); i>=(n); i--) #define pii pair<int,int> #define pll pair<ll,ll> #define MP make_pair #define fs first #define se second #define bit(msk, i) ((msk >> i) & 1) #define iter(id, v) for(auto id : v) #define pb push_back #define SZ(v) (ll)v.size() #define ALL(v) v.begin(),v.end() using namespace std; mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count()); ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); } const int N = 1e5 + 7; const int Mod = 1e9 + 7; const int INF = 1e9; const ll BASE = 137; const int szBL = 320; int n, m; map<pii,int> cnt, dd; queue<pii> pq; set<int> inS[N], outS[N], in[N]; ll numin[N]; ll res = 0; struct Disjoin_set { ll lab[N], sz[N]; void init (int n) { rep (i, 1, n) lab[i] = i, sz[i] = 1; } int Find (int u) { return u == lab[u] ? u : lab[u] = Find(lab[u]); } void add_edge (int u, int v) { int uu = Find(u), vv = Find(v); if (uu == vv) return; if (dd[{u, vv}] == 0) { dd[{u, vv}] = 1; cnt[{uu, vv}]++; numin[vv]++; res += sz[vv]; } if (inS[uu].find(vv) != inS[uu].end()) pq.push({uu, vv}); inS[vv].insert(uu); outS[uu].insert(vv); in[vv].insert(u); } void Join (int u, int v) { u = Find(u), v = Find(v); if (u == v) return; if (SZ(in[u]) + SZ(outS[u]) + SZ(inS[u]) < SZ(in[v]) + SZ(outS[v]) + SZ(inS[v])) swap(u, v); // cout << u <<" "<<v<<" hihi\n"; numin[u] -= cnt[{v, u}]; numin[v] -= cnt[{u, v}]; res -= sz[u] * (sz[u] - 1) + sz[v] * (sz[v] - 1); res -= sz[v] * cnt[{u, v}] + sz[u] * cnt[{v, u}]; // cout << res<<" "<<cnt[{3, 1}]<<" "<<cnt[{1, 3}]<<"\n"; res += (sz[u] + sz[v]) * (sz[u] + sz[v] - 1); res += numin[v] * sz[u] + numin[u] * sz[v]; numin[u] += numin[v]; iter (&id, in[v]) { if (Find(id) == v || Find(id) == u) continue; if (in[u].find(id) != in[u].end()) { res -= sz[u] + sz[v]; numin[u] --; } if (dd[{id, u}] == 0) { dd[{id, u}] = 1; cnt[{Find(id), u}]++; } } iter (&id, inS[v]) { if (id == u) continue; if (outS[u].find(id) != outS[u].end()) pq.push({id, u}); outS[id].erase(v), outS[id].insert(u); inS[u].insert(id); } iter (&id, outS[v]) { if (id == u) continue; if (inS[u].find(id) != inS[u].end()) pq.push({id, u}); cnt[{u, id}] += cnt[{v, id}]; inS[id].erase(v), inS[id].insert(u); outS[u].insert(id); } iter (&id, in[v]) { if (Find(id) == v || Find(id) == u) continue; dd[{id, u}] = 1; in[u].insert(id); } set<int> ().swap(inS[v]); set<int> ().swap(outS[v]); sz[u] += sz[v]; lab[v] = u; } void simulate () { while (!pq.empty()) { pii u = pq.front(); pq.pop(); Join(u.fs, u.se); } } }DSU; void solution () { cin >> n >> m; DSU.init(n); rep (i, 1, m) { int u, v; cin >> u >> v; DSU.add_edge(u, v); DSU.simulate(); cout << res <<"\n"; } } #define file(name) freopen(name".inp","r",stdin); \ freopen(name".out","w",stdout); int main () { // file("c"); ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0); int num_Test = 1; // cin >> num_Test; while (num_Test--) solution(); } /* no bug challenge +4 mình có muốn dùng mảng này không? 4 5 1 3 4 1 1 2 3 2 2 1 return->break */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...