oj.uz

답안 #692127

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
692127 2023-02-01T07:25:58 Z EthanKim8683 조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2) C++17
0 / 100
 5000 ms 11988 KB 
#include<bits/stdc++.h>
using namespace std;
using I=int;
using Lli=long long int;
const I N=100000;
const I M=300000;
pair<I,I>fols[M];
set<pair<I,I>>viss;
vector<I>mems[N];
set<I>incs[N],outs[N];
I pars[N];
Lli res=0;
I fnd(I i){
  if(pars[i]<0)return i;
  return pars[i]=fnd(pars[i]);
}
void uni(I a,I b){
  if((a=fnd(a))==(b=fnd(b)))return;
  if(pars[a]>pars[b])swap(a,b);
  res-=(Lli)-pars[a]*(-pars[a]-1);
  res-=(Lli)-pars[b]*(-pars[b]-1);
  res-=(Lli)-pars[a]*incs[a].size();
  res-=(Lli)-pars[b]*incs[b].size();
  for(auto c:incs[b]){
    outs[c].erase(b);
    if(fnd(c)!=a){
      outs[c].insert(a);
      incs[a].insert(c);
    }
  }
  for(auto c:mems[b]){
    for(auto it=outs[c].begin();it!=outs[c].end();){
      I d=*it;
      if(d==a){
        it=outs[c].erase(it);
        incs[a].erase(c);
      }
    }
    mems[a].push_back(c);
  }
  pars[a]+=pars[b],pars[b]=a;
  res+=(Lli)-pars[a]*(-pars[a]-1);
  res+=(Lli)-pars[a]*incs[a].size();
}
I main(){
  cin.tie(0)->sync_with_stdio(0);
  I n,m;cin>>n>>m;
  for(I i=0;i<m;i++){
    I a,b;cin>>a>>b,a--,b--;
    fols[i]={a,b};
  }
  fill_n(pars,n,-1);
  for(I i=0;i<n;i++)mems[i].push_back(i);
  for(I i=0;i<m;i++){
    auto[a,b]=fols[i];
    if(viss.count({b,a})){
      uni(a,b);
    }else{
      viss.insert({a,b});
      b=fnd(b);
      if(!outs[a].count(b)){
        outs[a].insert(b);
        incs[b].insert(a);
        res+=-pars[b];
      }
    }
    printf("%lli\n",res);
  }
}

Subtask #1
0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5036 ms 11988 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5036 ms 11988 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5036 ms 11988 KB Time limit exceeded
2 Halted 0 ms 0 KB -