Submission #734007

#	Time	Username	Problem	Language	Result	Execution time	Memory
734007		mosiashvililuka	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++14	0 / 100	1 ms	340 KiB

joitter2

#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,pas,t,tes,msh[100009],zm[100009],bo[2009][2009],FX[100009];
pair <int, int> P[300009];
int fnd(int q){
    if(msh[q]==0) return q; else return msh[q]=fnd(msh[q]);
}
void mrg(int q, int w){
    q=fnd(q);w=fnd(w);
    if(q==w) return;
    if(zm[q]<zm[w]) swap(q,w);
    msh[w]=q;
    zm[q]+=zm[w];
}
int main(){
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>a>>tes;
    for(i=1; i<=a; i++){
        zm[i]=1;
    }
    for(t=1; t<=tes; t++){
        cin>>c>>d;
        if(bo[c][d]==1) continue;
        bo[c][d]=1;
        P[t]={c,d};
        if(bo[d][c]==1){
            mrg(c,d);
        }
        for(i=1; i<=a; i++) FX[i]=0;
        pas=0;
        for(i=1; i<=a; i++){
            ii=fnd(i);
            if(FX[ii]==1) continue;
            pas+=zm[ii]*(zm[ii]-1);FX[ii]=1;
        }
        for(i=1; i<=a; i++){
            for(j=1; j<=a; j++) FX[j]=0;
            for(j=1; j<=a; j++){
                if(bo[i][j]==0) continue;
                ii=fnd(i);jj=fnd(j);
                if(ii==jj) continue;
                if(FX[jj]!=0) continue;
                FX[jj]=1;
                pas+=zm[jj];
            }
        }
        cout<<pas<<"\n";
    }
    return 0;
}

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