Submission #257779

#	Time	Username	Problem	Language	Result	Execution time	Memory
257779		Bruteforceman	Making Friends on Joitter is Fun (JOI20_joitter2)	C++11	1 / 100	5027 ms	11196 KiB

joitter2

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
set <int> in[maxn], out[maxn];
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);
}
void join(int x, int y) {
  x = root(x);
  y = root(y);
  if(in[x].size() + out[x].size() > in[y].size() + out[y].size()) swap(x, y); 
  if(x != y) {
//    cout << x << " " << y << endl;
    par[x] = y;
    sub[y] += sub[x];
    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);
    }
  }
}
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); 
    edge.emplace_back(p, 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 = 0;
    for(int i = 1; i <= n; i++) {
      if(root(i) == i) {
        ans += 1LL * sub[i] * (sub[i] - 1);
      }
    }
    set <pair <int, int>> s;
    for(auto i : edge) {
      if(root(i.first) != root(i.second)) {
        s.insert(make_pair(i.first, root(i.second)));
      }
    }
    for(auto i : s) ans += sub[i.second]; 
    printf("%lld\n", ans);
  }
}

Compilation message (stderr)

joitter2.cpp: In function 'int main()':
joitter2.cpp:40: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:48: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: 0 / 16
• Subtask 3: 0 / 83