제출 #212156

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
212156		DodgeBallMan	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++14	0 / 100	16 ms	19840 KiB

joitter2

#include <bits/stdc++.h>
#define pii pair<int, int>
#define x first
#define y second

using namespace std;

const int N = 1e5 + 10;
set<int> in[N], out[N], com[N], e[N];
long long ans;
int n, m, par[N], sz[N];

int find( int u ) { return par[u] == u ? u : par[u] = find( par[u] ); }

long long cal( int u ) { return 1LL * ( ( ( int )e[u].size() - sz[u] ) * sz[u] ) + 1LL * sz[u] * ( sz[u]-1 ); }

void merge( int a, int b ) {
    vector<pii> v;
    a = find( a ), b = find( b );
    if( a == b ) return ;
    if( in[a].size() + out[a].size() + e[a].size() < in[b].size() + out[b].size() + e[b].size() ) swap( a, b );
    ans -= cal( a ), ans -= cal( b );
    in[a].erase( b ), in[b].erase( a ), out[a].erase( b ), out[b].erase( a );
    for( int x : in[a] ) {
        if( out[b].count( x ) ) v.emplace_back( x, a );
        out[x].erase( a ), out[x].emplace( b );
    }
    for( int x : out[a] ) {
        if( in[b].count( x ) ) v.emplace_back( x, a );
        in[x].erase( a ), in[x].emplace( b );
    }
    for( int x : in[b] ) in[a].emplace( x );
    for( int x : out[b] ) out[a].emplace( x );
    for( int x : e[b] ) e[a].emplace( x );
    in[b].clear(), out[b].clear(), e[b].clear();
    sz[a] += sz[b], par[b] = a;
    ans += cal( a );
    for( pii x : v ) merge( x.x, x.y ); 
}

int main()
{
    scanf("%d %d",&n,&m);
    iota( par, par + N, 0 ), fill( sz, sz + N, 1 );
    for( int i = 1 ; i <= n ; i++ ) e[i].emplace( i );
    while( m-- ) {
        int u, v;
        scanf("%d %d",&u,&v);
        int a = find( u ), b = find( v );
        if( out[b].count( a ) ) merge( u, v );
        else {
            ans -= cal( b );
            in[b].emplace( a ), out[a].emplace( b );
            e[b].emplace( u );
            ans += cal( b );
        }
        printf("%lld\n",ans);
    }
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

joitter2.cpp: In function 'int main()':
joitter2.cpp:43:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&n,&m);
     ~~~~~^~~~~~~~~~~~~~~
joitter2.cpp:48:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&u,&v);
         ~~~~~^~~~~~~~~~~~~~~

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