Submission #257823

#	Time	Username	Problem	Language	Result	Execution time	Memory
257823		Bruteforceman	Making Friends on Joitter is Fun (JOI20_joitter2)	C++11	100 / 100	1876 ms	106248 KiB

joitter2

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
set <int> in[maxn], out[maxn];
set <pair <int, int>> incoming[maxn], outgoing[maxn];
set <int> cont[maxn];
long long edgeCnt;

queue <pair <int, int>> Q;
int par[maxn];
int sub[maxn];
int root(int x) {
  if(par[x] == x) return x;
  return par[x] = root(par[x]);
}
bool change(set <int> &t, set <int> &r, int i, int j) {
  t.erase(i); t.insert(j);
  return r.count(j);
}
long long totalCont(int i) {
  return 1LL * cont[i].size() * sub[i] + 1LL * sub[i] * (sub[i] - 1);
}
void join(int x, int y) {
  x = root(x);
  y = root(y);
  if(incoming[x].size() + outgoing[x].size() > incoming[y].size() + outgoing[y].size()) swap(x, y); 
  if(x != y) {
    for(int i : in[x]) {
      in[y].insert(i);
      if(change(out[i], in[i], x, y)) Q.emplace(i, y);
    }
    for(int i : out[x]) {
      out[y].insert(i);
      if(change(in[i], out[i], x, y)) Q.emplace(i, y);
    }
    edgeCnt -= totalCont(x) + totalCont(y);
    for(auto i : incoming[x]) {
      if(root(i.second) == y) {
        outgoing[y].erase(make_pair(i.second, i.first));
        continue;
      }
      incoming[y].insert(i);
      cont[y].insert(i.second);
    }
    for(auto i : outgoing[x]) {
      if(root(i.second) == y) {
        incoming[y].erase(make_pair(i.second, i.first));
        cont[y].erase(i.first);
        continue;
      }
      outgoing[y].insert(i);
    }
    par[x] = y;
    sub[y] += sub[x];
    edgeCnt += totalCont(y);
  }
}
bool exists(int i, int j) {
  i = root(i); j = root(j);
  return out[i].count(j);
}
int main() {
  int n, m;
  scanf("%d %d", &n, &m);
  for(int i = 1; i <= n; i++) {
    par[i] = i;
    sub[i] = 1;
  }
  vector <pair <int, int>> edge;
  for(int x = 1; x <= m; x++) {
    int p, q;
    scanf("%d %d", &p, &q); 
    if(root(p) != root(q)) {
      incoming[root(q)].insert(make_pair(q, p));
      outgoing[root(p)].insert(make_pair(p, q));
      edgeCnt -= totalCont(root(q));
      cont[root(q)].insert(p);
      edgeCnt += totalCont(root(q));
    }
    p = root(p);
    q = root(q);
    out[p].insert(q);
    in[q].insert(p);
    if(exists(p, q) && exists(q, p)) Q.emplace(root(p), root(q));
    while(!Q.empty()) {
      int p = Q.front().first;
      int q = Q.front().second;
      Q.pop();
      join(p, q);
    }
    long long ans = edgeCnt;
    printf("%lld\n", ans);
  }
}

Compilation message (stderr)

joitter2.cpp: In function 'int main()':
joitter2.cpp:64:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &n, &m);
   ~~~~~^~~~~~~~~~~~~~~~~
joitter2.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &p, &q); 
     ~~~~~^~~~~~~~~~~~~~~~~

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