oj.uz

답안 #734007

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
734007 2023-05-01T13:28:10 Z mosiashvililuka 조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2) C++14
0 / 100
 1 ms 340 KB 
#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.0

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

Subtask #2
0 / 16.0

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

Subtask #3
0 / 83.0

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