Submission #1070640

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070640		TraianDanciu	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	100 / 100	1578 ms	169420 KiB

joitter2

#include <stdio.h>
#include <vector>
#include <set>

#define MAXN 100000
#define MAXM 300000

struct Edge {
  int u, v;
} edges[MAXM];
int sef1[MAXN], sef2[MAXN], sz[MAXN];
std::set<int> flw[MAXN], muchii[MAXN];
std::set<std::pair<int, int>> mp;
std::vector<int> stiva;
long long rez;

static inline long long getrez(int i) {
  return 1LL * sz[i] * flw[i].size();
}

int find1(int i) {
  if(i == sef1[i]) {
    return i;
  }
  return sef1[i] = find1(sef1[i]);
}
void join1(int i, int j) {
  std::set<int>::iterator it;

  if((i = find1(i)) != (j = find1(j))) {
    if(sz[i] > sz[j]) {
      std::swap(i, j);
    }

    rez -= getrez(i) + getrez(j);
    sz[j] += sz[i];
    sef1[i] = j;

    if(flw[j].size() < flw[i].size()) {
      std::swap(flw[i], flw[j]);
    }
    it = flw[i].begin();
    while(it != flw[i].end()) {
      flw[j].insert(*it);
      it++;
    }

    rez += getrez(j);
  }
}

int find2(int i) {
  if(i == sef2[i]) {
    return i;
  }
  return sef2[i] = find2(sef2[i]);
}
void join2(int i, int j) {
  std::set<int>::iterator it;

  if((i = find2(i)) != (j = find2(j))) {
    join1(i, j);

    if(muchii[j].size() < muchii[i].size()) {
      std::swap(i, j);
    }
    it = muchii[i].begin();
    while(it != muchii[i].end()) {
      stiva.push_back(*it);
      muchii[j].insert(*it);
      it++;
    }

    sef2[i] = j;
  }
}

int main() {
  int n, m, i, u, v;

  scanf("%d%d", &n, &m);
  for(i = 0; i < n; i++) {
    sef1[i] = sef2[i] = i;
    flw[i].insert(i);
    sz[i] = 1;
  }

  rez = n;
  for(i = 0; i < m; i++) {
    scanf("%d%d", &edges[i].u, &edges[i].v);

    u = --edges[i].u;
    v = find1(--edges[i].v);
    rez -= getrez(v);
    flw[v].insert(u);
    rez += getrez(v);

    stiva.push_back(i);
    while(!stiva.empty()) {
      muchii[u = find2(edges[stiva.back()].u)].insert(stiva.back());
      muchii[v = find2(edges[stiva.back()].v)].insert(stiva.back());
      stiva.pop_back();

      mp.insert(std::make_pair(u, v));
      if(mp.count(std::make_pair(v, u))) {
        join2(u, v);
      }
    }

    printf("%lld\n", rez - n);
  }

  return 0;
}

Compilation message (stderr)

joitter2.cpp: In function 'int main()':
joitter2.cpp:81:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |   scanf("%d%d", &n, &m);
      |   ~~~~~^~~~~~~~~~~~~~~~
joitter2.cpp:90:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |     scanf("%d%d", &edges[i].u, &edges[i].v);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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