Submission #173448

#	Time	Username	Problem	Language	Result	Execution time	Memory
173448		easrui	우호 조약 체결 (JOI14_friends)	C++14	100 / 100	760 ms	12252 KiB

friends

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MN = 2e5+5;

int N,M,s,e,D[MN],cur,par[MN];
ll sz[MN],ans;
vector<int> G[MN];
bool ch[MN];

int fnd(int s)
{
    return par[s]==s ? s : par[s]=fnd(par[s]);
}

void join(int x, int y)
{
    x = fnd(x), y = fnd(y);
    if(x==y) return;
    par[y] = x;
    sz[x] += sz[y];
}

void act(int s)
{
    int p = 0;
    if(sz[fnd(s)]>1) p = s;
    for(int e : G[s]){
        if(p) join(e,p);
        p = e;
    }
}

int main()
{
    cin >> N >> M;
    for(int i=1; i<=N; i++) par[i] = i, sz[i] = 1;
    for(int i=0; i<M; i++){
        cin >> s >> e;
        G[s].push_back(e);
        D[s]++;
        if(D[s]>D[cur]) cur = s;
    }
    for(int j=1; j<=100; j++)
        for(int i=1; i<=N; i++) act(i);
    for(int i=1; i<=N; i++){
        if(par[i]==i) ans += sz[i]*(sz[i]-1);
        for(int e : G[i]) if(fnd(i)!=fnd(e)) ans++;
    }
    cout << ans;
}

• Subtask 1: 5 / 5
• Subtask 2: 30 / 30
• Subtask 3: 65 / 65