제출 #212760

#제출 시각아이디문제언어결과실행 시간메모리
212760Alexa2001조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)C++17
0 / 100
15 ms16896 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int Nmax = 1e5 + 5; set<int> in[Nmax], cIn[Nmax], cOut[Nmax]; vector<int> who[Nmax]; int n, m; int where[Nmax]; ll ans = 0; ll take2(int x) { return (ll) x * (x-1); } void unite(int x, int y) { if(x == y) return; if(cIn[x].find(y) == cIn[x].end() || cOut[x].find(y) == cOut[x].end()) return; if(who[x].size() + in[x].size() + cIn[x].size() + cOut[x].size() < who[y].size() + in[y].size() + cIn[y].size()) swap(x, y); ans -= take2(who[x].size()); ans -= take2(who[y].size()); ans += take2(who[x].size() + who[y].size()); ans -= (ll) who[x].size() * in[x].size(); ans -= (ll) who[y].size() * in[y].size(); // for(auto it : in[x]) cerr << it << ' '; cerr << "#\n"; // for(auto it : in[y]) cerr << it << ' '; cerr << "#\n"; for(auto it : who[y]) if(in[x].find(it) != in[x].end()) in[x].erase(it); for(auto it : in[y]) if(where[it] != x) in[x].insert(it); for(auto it : who[y]) { who[x].push_back(it); where[it] = x; } for(auto it : cOut[y]) if(it != x) { cIn[it].erase(y); cIn[it].insert(x); cOut[x].insert(it); } for(auto it : cIn[y]) if(it != x) { cOut[it].erase(y); cOut[it].insert(x); cIn[x].insert(it); } ans += (ll) who[x].size() * in[x].size(); for(auto it : cIn[y]) unite(x, it); for(auto it : cOut[y]) unite(x, it); who[y].clear(); in[y].clear(); cIn[y].clear(); cOut[y].clear(); } void compute(int X, int Y) { int x, y; x = where[X]; y = where[Y]; if(x == y) return; auto itt = in[y].insert(X); if(itt.second) { ans += who[y].size(); cIn[y].insert(x); cOut[x].insert(y); } unite(x, y); } int main() { // freopen("input", "r", stdin); cin.sync_with_stdio(false); cin.tie(0); cin >> n >> m; for(int i=1; i<=n; ++i) { where[i] = i; who[i].push_back(i); } for(int i=1; i<=m; ++i) { int x, y; cin >> x >> y; compute(x, y); cout << ans << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...