제출 #706793

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
706793		EthanKim8683	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	1 / 100	5081 ms	55252 KiB

joitter2

#include<bits/stdc++.h>
using namespace std;
using I=int;
using Lli=long long int;
const I N=100000;
set<I>incs[N],outs[N];
Lli res=0;
void add(I a,I b){
  if(a==b)return;
  if(outs[a].count(b))return;
  outs[a].insert(b);
  incs[b].insert(a);
  res++;
  vector<I>adds;
  do{
    adds.clear();
    for(auto c:outs[b]){
      if(!outs[c].count(b))continue;
      if(a==c)continue;
      if(outs[a].count(c))continue;
      adds.push_back(c);
    }
    for(auto c:adds)add(a,c);
  }while(adds.size());
  if(outs[b].count(a)){
    for(auto c:incs[a])add(c,b);
    for(auto c:incs[b])add(c,a);
  }
}
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--;
    add(a,b);
    printf("%lli\n",res);
  }
}

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