Submission #1193944

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193944		comgaTramAnh	Making Friends on Joitter is Fun (JOI20_joitter2)	C++20	0 / 100	5094 ms	14408 KiB

joitter2

#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::ios_base::sync_with_stdio(false);
  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; 
}

• Subtask 1: 0 / 1
• Subtask 2: 0 / 16
• Subtask 3: 0 / 83