Submission #772230

#	Time	Username	Problem	Language	Result	Execution time	Memory
772230		vjudge1	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	100 / 100	1424 ms	103548 KiB

joitter2

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

void __print(int x) {cout << x;}
void __print(long x) {cout << x;}
void __print(long long x) {cout << x;}
void __print(unsigned x) {cout << x;}
void __print(unsigned long x) {cout << x;}
void __print(unsigned long long x) {cout << x;}
void __print(float x) {cout << x;}
void __print(double x) {cout << x;}
void __print(long double x) {cout << x;}
void __print(char x) {cout << '\'' << x << '\'';}
void __print(const char *x) {cout << '\"' << x << '\"';}
void __print(const string &x) {cout << '\"' << x << '\"';}
void __print(bool x) {cout << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cout << '{'; __print(x.first); cout << ','; __print(x.second); cout << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cout << '{'; for (auto &i: x) cout << (f++ ? "," : ""), __print(i); cout << "}";}
void _print() {cout << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cout << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cout << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...) 
#endif

const int MAXN = 1e5 + 5;
int n, m;
ll followings = 0;
set<int> adj[MAXN], radj[MAXN], child[MAXN];
vector<int> parent(MAXN), sz(MAXN);
queue<pair<int,int>> q;

void init(int v) {
  parent[v] = v;
  sz[v] = 1;
  child[v].insert(v);
}

int find(int v) {
  if (parent[v] == v)
    return v;
  return parent[v] = find(parent[v]);
}

int totalSize(int v) {
  int s = adj[v].size() + radj[v].size() + child[v].size();
  return s;
}

void follow(int a, int b) {
  adj[a].insert(b);
  radj[b].insert(a);
  if (adj[b].find(a) != adj[b].end()) {
    q.push({a, b});
  }
}

void mutualFollow(int a, int b) {
  a = find(a), b = find(b);
  if (a == b) return;
  if (totalSize(a) < totalSize(b)) swap(a, b);
  followings += sz[a] * child[b].size() + sz[b] * child[a].size();
  parent[b] = a;
  sz[a] += sz[b];
  for (int i : child[b]) {
    if (child[a].find(i) == child[a].end()) {
      child[a].insert(i);
    } else {
      followings -= sz[a];
    }
  }
  adj[a].erase(b);
  adj[b].erase(a);
  radj[a].erase(b);
  radj[b].erase(a);
  for (int i : adj[b]) {
    follow(a, i);
  }
  for (int i : radj[b]) {
    follow(i, a); 
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    init(i);
  }
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    int compA = find(a), compB = find(b);
    if (compA != compB && child[compB].find(a) == child[compB].end()) {
      child[compB].insert(a);
      followings += sz[compB];
      follow(compA, compB);
      while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        mutualFollow(x, y);
      }
    }
    cout << followings << "\n";
  }

  return 0;
}

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