Submission #1282665

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282665		artrivas	Making Friends on Joitter is Fun (JOI20_joitter2)	C++20	0 / 100	2 ms	4920 KiB

joitter2

#include<bits/stdc++.h>
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef pair<ll,ll> pl;

#define forr(i,a,b) for(int i=int(a);i<int(b);++i)
#define forn(i,n) forr(i,0,n)
#define dforr(i,a,b) for(int i=int(b)-1;i>=int(a);--i)
#define dforn(i,n) dforr(i,0,n)
#define fore(e,c) for(const auto &e : (c))
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define fi first
#define se second

const ll MAXN = 5e4+1;
const ll mod = 1e9+7;
const ll inf = 1e18+10;

ll n,m;

ll parent[MAXN];
ll sz[MAXN];
map<ll,bool> edges[MAXN];
set<ll> entrantes[MAXN];
ll cnt = 0;
void make_parents(){
  for(ll i = 0; i < n; ++i){
    sz[i] = 1;
    parent[i] = i;
  }
}
ll find_parent(ll x){
  if(x == parent[x])
    return x;
  return parent[x] = find_parent(parent[x]);
}
void merge(ll a, ll b){
  ll s_a = find_parent(a);
  ll s_b = find_parent(b);
  if( s_a != s_b && entrantes[s_b].find(a) == entrantes[s_b].end() ){
    cnt += sz[s_b];
    edges[s_a][s_b] = true;
    if(a == 5-1 && b == 4-1){
      //cout << s_a << ' ' << s_b << '\n';

    }
    if(edges[s_b].find(a) == edges[s_b].end()){
      entrantes[s_b].insert(a);
    }else{
      auto itr = entrantes[s_a].begin();
      ll xd = 0;
      while(itr != entrantes[s_a].end()){
        auto current = itr++;
        if(find_parent(*current) == s_b){
          ++xd;
          entrantes[s_a].erase(current);
        }
      }
      if(sz[s_a] < sz[s_b]){
        swap(a,b);
      }
      /*cout << "xd: "<<s_a +1 << ' ' << s_b +1 << '\n';
      cout << "xd: "<<entrantes[s_a].size() << ' ' << sz[s_a]<<'\n';
      for(auto i : entrantes[s_a])
        cout << i+1 << ' ';
      cout << '\n';
      cout << "xd: "<<entrantes[s_b].size() << ' ' << sz[s_b]<<'\n';
      for(auto i : entrantes[s_b])
        cout << i+1 << ' ';
      cout << '\n';
      cout<<entrantes[s_a].size()*sz[s_b] + entrantes[s_b].size()*sz[s_a] << '\n';*/
      cnt+=entrantes[s_a].size()*sz[s_b] + entrantes[s_b].size()*sz[s_a];
      cnt+=2LL*sz[s_a]*sz[s_b]-xd*sz[s_a]-sz[s_b];
      for(auto i : entrantes[s_b]){
        if(entrantes[s_a].find(i) != entrantes[s_a].end()){
          cnt-=sz[s_a]+sz[s_b];
        }else{
          entrantes[s_a].insert(i);
        }
      }
      for(auto i : edges[s_b]){
        edges[s_a].insert(i);
      }
      sz[s_a]+=sz[s_b];
      parent[s_b] = s_a;
    }
  }
}

void solve(){
  cin >> n >> m;
  make_parents();
  for(ll i = 0; i < m; ++i){
    ll n1,n2;
    cin >> n1 >> n2;
    merge(n1-1,n2-1);
    cout << cnt << '\n';
  }
}

int main(){
  ios::sync_with_stdio(0); cin.tie(0);
  int tt = 1;
  //freopen("disrupt.in", "r", stdin);
  //freopen("disrupt.out", "w", stdout);
  //cin >> tt;
  while(tt--) solve();
  return 0;
}

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