Submission #234927

#	Time	Username	Problem	Language	Result	Execution time	Memory
234927		AlexLuchianov	Making Friends on Joitter is Fun (JOI20_joitter2)	C++14	1 / 100	11 ms	4992 KiB

joitter2

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

using ll = long long;

#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 20000;
int v[1 + nmax][2];

ll total = 0;

void _add(set<int> &myset1, set<int> &myset2){
  if(myset1.size() < myset2.size())
    swap(myset1, myset2);
  for(set<int>::iterator it = myset2.begin(); it != myset2.end(); it++)
    myset1.insert(*it);
}

namespace Dsu{
  vector<int> mult;
  vector<int> sz;
  set<int> followers[1 + nmax];

  void initialize(int n){
    mult.resize(1 + n);
    sz.resize(1 + n);
    for(int i = 1;i <= n; i++) {
      mult[i] = i;
      sz[i] = 1;
      followers[i].insert(i);
    }
  }

  int jump(int gala){
    if(mult[gala] != gala)
      mult[gala] = jump(mult[gala]);
    return mult[gala];
  }

  ll extract(int gala){
    return 1LL * sz[gala] * followers[gala].size();
  }

  void unite(int gala, int galb){
    gala = jump(gala);
    galb = jump(galb);
    if(gala == galb)
      return ;
    if(sz[galb] < sz[gala])
      swap(gala, galb);
    total += - extract(gala) - extract(galb);
    sz[galb] += sz[gala];
    mult[gala] = galb;
    _add(followers[galb], followers[gala]);
    total += extract(galb);
  }

  void addfollow(int x, int y){
    y = jump(y);
    total -= extract(y);
    followers[y].insert(x);
    total += extract(y);
  }
}

namespace Dsu2{
  vector<int> mult;
  set<int> adj[1 + nmax];
  set<pair<int,int>> freq;

  void initialize(int n){
    mult.resize(1 + n);
    for(int i = 1; i <= n; i++)
      mult[i] = i;
  }

  int jump(int gala) {
    if(mult[gala] != gala)
      mult[gala] = jump(mult[gala]);
    return mult[gala];
  }

  vector<int> st;

  void unite(int gala, int galb){
    gala = jump(gala);
    galb = jump(galb);
    if(gala == galb)
      return ;
    Dsu::unite(gala, galb);
    if(adj[galb].size() < adj[gala].size())
      swap(gala, galb);
    for(set<int>::iterator it = adj[gala].begin(); it != adj[gala].end(); it++)
      st.push_back(*it);
    _add(adj[galb], adj[gala]);
    mult[gala] = galb;
  }

  void refresh(){
    while(0 < st.size()){
      int id = st.back();
      int x = jump(v[id][0]);
      int y = jump(v[id][1]);
      adj[x].insert(id);
      adj[y].insert(id);

      freq.insert({x, y});
      st.pop_back();

      if(freq.find({y, x}) != freq.end())
        unite(x, y);
    }
  }
}

void activate(int id){
  int x = v[id][0];
  int y = v[id][1];
  Dsu::addfollow(x, y);
  Dsu2::st.push_back(id);
  Dsu2::refresh();
}

int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);

  int n, q;
  cin >> n >> q;
  total = n;
  for(int i = 1;i <= q; i++)
    cin >> v[i][0] >> v[i][1];
  Dsu::initialize(n);
  Dsu2::initialize(n);

  for(int i = 1;i <= q; i++){
    activate(i);
    cout << total - n<< '\n';
  }
  return 0;
}

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