Submission #834598

#	Time	Username	Problem	Language	Result	Execution time	Memory
834598		NemanjaSo2005	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	100 / 100	1061 ms	87948 KiB

joitter2

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+5;
int N,M;
ll rod[maxn],vel[maxn];
ll res;
set<int> cukomp[maxn],kompuc[maxn],compout[maxn],compin[maxn];
vector<int> koji[maxn];
queue<pair<int,int>> Q;
int getpar(int x){
   if(rod[x]==x)
      return x;
   rod[x]=getpar(rod[x]);
   return rod[x];
}
void pretvori(int a,int b){
   for(auto it=kompuc[a].begin();it!=kompuc[a].end();it++){
      cukomp[*it].erase(a);
      if(getpar(*it)!=b)
         cukomp[*it].insert(b);
   }
  // cout<<"A"<<endl;
   for(auto it=compout[a].begin();it!=compout[a].end();it++){
      compin[*it].erase(a);
      compin[*it].insert(b);
   }
   //cout<<"B"<<endl;
   for(auto it=compin[a].begin();it!=compin[a].end();it++){
      compout[*it].erase(a);
      compout[*it].insert(b);
   }
  // cout<<"C"<<endl;
}
void spoj(int a,int b){ /// a i b su indeksi komponenti
   if(getpar(a)!=a or getpar(b)!=b)
      return;
   if(vel[b]>vel[a])
      swap(a,b);
   //cout<<"SPAJAM "<<a<<" "<<b<<endl;
   res-=vel[a]*kompuc[a].size();
   res-=vel[a]*(vel[a]-1);
   res-=vel[b]*kompuc[b].size();
   res-=vel[b]*(vel[b]-1);
   //cout<<res<<endl;
   compin[a].erase(b);
   compout[a].erase(b);
   compin[b].erase(a);
   compout[b].erase(a);
   //cout<<"OVDE"<<endl;
   vel[a]+=vel[b];
   rod[b]=a;
   pretvori(b,a);
  // cout<<"OKK"<<endl;
   for(int i=0;i<koji[b].size();i++){
      kompuc[a].erase(koji[b][i]);
      koji[a].push_back(koji[b][i]);
   }
   for(auto it=compin[b].begin();it!=compin[b].end();it++){
      if(compout[a].find(*it)!=compout[a].end())
         Q.push({getpar(*it),getpar(a)});
      compin[a].insert(*it);
   }
   for(auto it=compout[b].begin();it!=compout[b].end();it++){
      if(compin[a].find(*it)!=compin[a].end())
         Q.push({getpar(a),getpar(*it)});
      compout[a].insert(*it);
   }
   for(auto it=kompuc[b].begin();it!=kompuc[b].end();it++)
      if(getpar(*it)!=a)
         kompuc[a].insert(*it);
   res+=vel[a]*(vel[a]-1);
   res+=vel[a]*kompuc[a].size();
  // cout<<vel[a]<<" "<<kompuc[a].size()<<endl;
   return;
}
void odradi(int a,int b){
   //cout<<a<<" "<<b<<endl;
   int ca=getpar(a);
   int cb=getpar(b);
   if(ca==cb)
      return;
   if(cukomp[a].find(cb)!=cukomp[a].end())
      return;
   if(compout[cb].find(ca)!=compout[cb].end()){
     // cout<<"SPAJAJ"<<endl;
      spoj(ca,cb);
      return;
   }
   res+=vel[cb];
   cukomp[a].insert(cb);
   kompuc[cb].insert(a);
   compin[cb].insert(ca);
   compout[ca].insert(cb);
   return;
}
int main(){
   ios_base::sync_with_stdio(false);
   cin.tie(0);
   cin>>N>>M;
   for(int i=1;i<=N;i++){
      vel[i]=1;
      rod[i]=i;
      koji[i].push_back(i);
   }
   res=0;
   int a,b;
   while(M--){
      cin>>a>>b;
      odradi(a,b);
      while(Q.size()){
         spoj(Q.front().first,Q.front().second);
         Q.pop();
      }
      cout<<res<<"\n";
   }
   return 0;
}

Compilation message (stderr)

joitter2.cpp: In function 'void spoj(int, int)':
joitter2.cpp:55:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |    for(int i=0;i<koji[b].size();i++){
      |                ~^~~~~~~~~~~~~~~

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