Submission #384134

#	Time	Username	Problem	Language	Result	Execution time	Memory
384134		qwerty234	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++14	0 / 100	75 ms	113004 KiB

joitter2

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
using namespace std;

const int MAXN = 4e5 + 10;

multiset <int> out[MAXN], in[MAXN], out_set[MAXN], in_set[MAXN];
multiset <pair<int, int>> out_edge[MAXN], in_edge[MAXN];
multiset <int>::iterator it;
multiset <pair<int, int>>::iterator itt;
int n, m, ptr[MAXN], p[MAXN], sz[MAXN];
ll ans;

void make_set() {
  for (int i = 1; i <= n; i++) {
    p[i] = i; sz[i] = 1;
    out[i].clear(); in[i].clear(); out_set[i].clear(); in_set[i].clear();
    out_edge[i].clear(); in_edge[i].clear();
    ptr[i] = i;
  }
  ans = 0;
}

int getp(int u) {
  if (p[u] == u)
    return u;
  return p[u] = getp(p[u]);
}

void un(int u, int v) {
  u = getp(u); v = getp(v);
  if (u == v)
    return;
  if (sz[u] + out[ptr[u]].size() + in[ptr[u]].size() + out_set[ptr[u]].size() + in_set[ptr[u]].size() > sz[v] + out[ptr[v]].size() + in[ptr[v]].size() + out_set[ptr[v]].size() + in_set[ptr[v]].size())
    swap(u, v);
  int cu = 0, cv = in[ptr[v]].size();
  ans += (ll)sz[u] * (ll)sz[v] * 2ll;
  for (it = out[ptr[u]].begin(); it != out[ptr[u]].end(); it++) {
    int to = *it;
    if (getp(to) == v) {
      ans -= (ll)sz[v];
      cv--;
    }
  }
  for (it = in[ptr[u]].begin(); it != in[ptr[u]].end(); it++) {
    int to = *it;
    if (getp(to) == v) {
      ans -= (ll)sz[u];
    } else {
      if (in[ptr[v]].count(to))
        cv--;
      else
        cu++;
    }
  }
  ans += (ll)cu * (ll)sz[v] + (ll)cv * (ll)sz[u];
  p[u] = v;
  sz[v] += sz[u];
  set <pair<int, int>> tocon; tocon.clear();
  for (itt = out_edge[ptr[u]].begin(); itt != out_edge[ptr[u]].end(); itt++) {
    pair<int, int> tmp = *itt;
    int t1 = tmp.fi, t2 = tmp.se;
    if (getp(t2) == v) {
      in[ptr[v]].erase(t1);
      in_edge[ptr[v]].erase(tmp);
    } else {
      out[ptr[v]].insert(t2);
      out_edge[ptr[v]].insert(tmp);
    }
  }
  for (itt = in_edge[ptr[u]].begin(); itt != in_edge[ptr[u]].end(); itt++) {
    pair<int, int> tmp = *itt;
    int t1 = tmp.fi, t2 = tmp.se;
    if (getp(t1) == v) {
      out[ptr[v]].erase(t2);
      out_edge[ptr[v]].erase(tmp);
    } else {
      in[ptr[v]].insert(t1);
      in_edge[ptr[v]].insert(tmp);
    }
  }
  for (it = out[ptr[u]].begin(); it != out[ptr[u]].end(); it++) {
    int to = *it;
    if (getp(to) == v)
      in[ptr[v]].erase(to);
    else
      out[ptr[v]].insert(to);
  }
  for (it = in_set[ptr[u]].begin(); it != in_set[ptr[u]].end(); it++) {
    int to = *it;
    in_set[ptr[v]].insert(to);
    out_set[ptr[to]].insert(v);
    out_set[ptr[to]].erase(u);
    if (out_set[ptr[v]].count(to))
      tocon.insert({v, to});
  }
  for (it = out_set[ptr[u]].begin(); it != out_set[ptr[u]].end(); it++) {
    int to = *it;
    out_set[ptr[v]].insert(to);
    in_set[ptr[to]].insert(v);
    in_set[ptr[to]].erase(u);
    if (in_set[ptr[v]].count(to))
      tocon.insert({v, to});
  }
  in[ptr[u]].clear(); out[ptr[u]].clear(); in_set[ptr[u]].clear(); out_set[ptr[u]].clear();
  in_edge[ptr[u]].clear(); out_edge[ptr[u]].clear();
  for (itt = tocon.begin(); itt != tocon.end(); itt++) {
    pair<int, int> tmp = *itt;
    un(tmp.fi, tmp.se);
  }
}

void connect(int u, int v) {
  int ru = u, rv = v;
  u = getp(u); v = getp(v);
  if (u == v || in[ptr[v]].count(ru))
    return;
  ans += (ll)sz[v];
  out[ptr[u]].insert(rv);
  out_edge[ptr[u]].insert({ru, rv});
  in[ptr[v]].insert(ru);
  in_edge[ptr[v]].insert({ru, rv});
  out_set[ptr[u]].insert(v);
  in_set[ptr[v]].insert(u);
  if (in_set[ptr[u]].count(v))
    un(u, v);
}

main() {
//  freopen("input.txt", "r", stdin);
  scanf("%d %d", &n, &m);
  make_set();
  for (int i = 1; i <= m; i++) {
    int u, v;
    scanf("%d %d", &u, &v);
    connect(u, v);
    printf("%lld\n", ans);
  }
}

Compilation message (stderr)

joitter2.cpp:132:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  132 | main() {
      |      ^
joitter2.cpp: In function 'int main()':
joitter2.cpp:134:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  134 |   scanf("%d %d", &n, &m);
      |   ~~~~~^~~~~~~~~~~~~~~~~
joitter2.cpp:138:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  138 |     scanf("%d %d", &u, &v);
      |     ~~~~~^~~~~~~~~~~~~~~~~

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