제출 #1193941

#제출 시각아이디문제언어결과실행 시간메모리
1193941comgaTramAnhMaking Friends on Joitter is Fun (JOI20_joitter2)C++20
0 / 100
5093 ms14408 KiB
#include <iostream> #include <algorithm> #include <vector> #include <set> #include <utility> int n, m; std::set <int> listIn[100005], listOut[100005], child[100005]; long long ans = 0LL; int root[100005]; int numb[100005]; void addEdge(int rootu, int rootv); void unite(int rootu, int rootv); int numbVertexInComponent(int u) { return (int) child[u].size() + (int) listIn[u].size() + (int) listOut[u].size(); } bool compare(int u, int v) { return numbVertexInComponent(u) < numbVertexInComponent(v); } int findRoot(int u) { return root[u] = (u == root[u] ? u : findRoot(root[u])); } void addEdge(int rootu, int rootv) { listOut[rootu].insert(rootv); listIn[rootv].insert(rootu); if (listOut[rootv].find(rootu) != listOut[rootv].end()) { unite(rootu, rootv); } } void unite(int rootu, int rootv) { if (rootu == rootv) { return; } if (compare(rootu, rootv) == true) { std::swap(rootu, rootv); } ans += (long long) child[rootu].size() * numb[rootv] + (long long) child[rootv].size() * numb[rootu]; numb[rootu] += numb[rootv]; root[rootv] = rootu; if (listOut[rootu].find(rootv) != listOut[rootu].end()) { listOut[rootu].erase(listOut[rootu].find(rootv)); } if (listOut[rootv].find(rootu) != listOut[rootv].end()) { listOut[rootv].erase(listOut[rootv].find(rootu)); } if (listIn[rootu].find(rootv) != listIn[rootu].end()) { listIn[rootu].erase(listIn[rootu].find(rootv)); } if (listIn[rootv].find(rootu) != listIn[rootv].end()) { listIn[rootv].erase(listIn[rootv].find(rootu)); } for (std::set <int>::iterator it = listOut[rootv].begin(); it != listOut[rootv].end(); it++) { listOut[rootu].insert(*it); } listOut[rootv].clear(); for (std::set <int>::iterator it = listIn[rootv].begin(); it != listIn[rootv].end(); it++) { listIn[rootu].insert(*it); } listIn[rootv].clear(); for (std::set <int>::iterator it = child[rootv].begin(); it != child[rootv].end(); it++) { if (child[rootu].find(*it) != child[rootu].end()) { ans -= numb[rootu]; } else { child[rootu].insert(*it); } } child[rootv].clear(); for (std::set <int>::iterator it = listIn[rootu].begin(); it != listIn[rootu].end(); it++) { int in = *it; addEdge(in, rootu); } for (std::set <int>::iterator it = listOut[rootu].begin(); it != listOut[rootu].end(); it++) { int out = *it; addEdge(rootu, out); } } int main () { std::cin >> n >> m; for (int i = 1; i <= n; i++) { root[i] = i; numb[i] = 1; child[i].insert(i); } for (int i = 1; i <= m; i++) { int u, v; std::cin >> u >> v; int rootu = findRoot(u); int rootv = findRoot(v); if (rootu == rootv || child[rootv].find(u) != child[rootv].end()) { std::cout << ans << std::endl; continue; } child[rootv].insert(u); ans += numb[rootv]; addEdge(rootu, rootv); std::cout << ans << std::endl; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...