oj.uz

답안 #706587

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
706587 2023-03-07T06:06:26 Z EthanKim8683 조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2) C++17
0 / 100
 7 ms 14420 KB 
#include<bits/stdc++.h>
using namespace std;
using I=int;
using Lli=long long int;
const I N=100000;
set<pair<I,I>>viss;
set<I>unqs[N];
map<I,I>incs[N],outs[N];
I tots[N];
I pars[N];
Lli res=0;
I fnd(I i){
  return pars[i]<0?i:pars[i]=fnd(pars[i]);
}
I siz(I i){
  return-pars[fnd(i)];
}
void uni(I a,I b){
  if((a=fnd(a))==(b=fnd(b)))return;
  if(pars[a]>pars[b])swap(a,b);
  Lli siz1=siz(a),siz2=siz(b);
  res-=siz1*(siz1-1);
  res-=siz2*(siz2-1);
  res-=tots[a]*siz1;
  res-=tots[b]*siz2;
  for(auto c:unqs[b]){
    unqs[a].insert(c);
  }
  for(auto[c,cnt]:incs[b]){
    outs[c].erase(b);
    tots[b]-=cnt;
    if(c!=a){
      outs[c][a]+=cnt;
      incs[a][c]+=cnt;
      tots[a]+=cnt;
    }
  }
  for(auto[c,cnt]:outs[b]){
    incs[c].erase(b);
    tots[c]-=cnt;
    if(c!=a){
      incs[c][a]+=cnt;
      outs[a][c]+=cnt;
      tots[c]+=cnt;
    }
  }
  unqs[b].clear();
  incs[b].clear();
  outs[b].clear();
  pars[a]+=pars[b],pars[b]=a;
  Lli siz3=siz(a);
  res+=siz3*(siz3-1);
  res+=tots[a]*siz3;
}
I main(){
  cin.tie(0)->sync_with_stdio(0);
  I n,m;cin>>n>>m;
  fill_n(pars,n,-1);
  for(I i=0;i<m;i++){
    I a,b;cin>>a>>b,a--,b--;
    I c=fnd(a),d=fnd(b);
    if(!unqs[d].count(a)){
      unqs[d].insert(a);
      incs[d][c]++;
      outs[c][d]++;
      tots[d]++;
      res+=siz(d);
    }
    viss.insert({a,b});
    if(viss.count({b,a}))uni(a,b);
    printf("%lli\n",res);
  }
}

Subtask #1
0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 14420 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 14420 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 14420 KB Output isn't correct
2 Halted 0 ms 0 KB -