oj.uz

Submission #834503

# Submission time Handle Problem Language Result Execution time Memory
834503 2023-08-22T15:03:58 Z NemanjaSo2005 Making Friends on Joitter is Fun (JOI20_joitter2) C++17
0 / 100
 13 ms 21460 KB 
#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(vel[b]>vel[a])
      swap(a,b);
   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({*it,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({a,*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(){
   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

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

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 21332 KB Output is correct
2 Correct 10 ms 21436 KB Output is correct
3 Correct 11 ms 21460 KB Output is correct
4 Correct 9 ms 21368 KB Output is correct
5 Correct 10 ms 21460 KB Output is correct
6 Correct 10 ms 21332 KB Output is correct
7 Incorrect 13 ms 21460 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 21332 KB Output is correct
2 Correct 10 ms 21436 KB Output is correct
3 Correct 11 ms 21460 KB Output is correct
4 Correct 9 ms 21368 KB Output is correct
5 Correct 10 ms 21460 KB Output is correct
6 Correct 10 ms 21332 KB Output is correct
7 Incorrect 13 ms 21460 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 21332 KB Output is correct
2 Correct 10 ms 21436 KB Output is correct
3 Correct 11 ms 21460 KB Output is correct
4 Correct 9 ms 21368 KB Output is correct
5 Correct 10 ms 21460 KB Output is correct
6 Correct 10 ms 21332 KB Output is correct
7 Incorrect 13 ms 21460 KB Output isn't correct
8 Halted 0 ms 0 KB -