oj.uz

답안 #961700

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
961700 2024-04-12T10:42:00 Z danikoynov 조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2) C++14
0 / 100
 1 ms 604 KB 
#include <bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

const int maxn = 2010;

int n, par[maxn], m;

int find_leader(int v)
{
    if (par[v] == v)
        return v;
    return (par[v] = find_leader(par[v]));
}

int sz[maxn];
set < int > in_adj[maxn], out_adj[maxn];

ll calc(int v)
{
    ll s = sz[v];
    return s * (s - 1 + (ll)(in_adj[v].size()));
}
void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++)
    {
        par[i] = i;
        sz[i] = 1;
    }
    ll edges = 0;
    for (int i = 1; i <= m; i ++)
    {
        int v, u;
        cin >> v >> u;
        int lv = find_leader(v), lu = find_leader(u);
        if (lv == lu)
        {
            cout << edges << endl;
            continue;
        }
        edges = edges - calc(find_leader(v));
        edges = edges - calc(find_leader(u));



        if (in_adj[lv].find(lu) != in_adj[lv].end())
        {
            in_adj[lv].erase(lu);
            vector < int > rem;
            for (int w : in_adj[lv])
            {
                 if (find_leader(w) == lu)
                    rem.push_back(w);
            }
            for (int w : rem)
               in_adj[lv].erase(w);
            for (int u : in_adj[lu])
                in_adj[lv].insert(u);
            sz[lv] += sz[lu];

            par[lu] = lv;
            edges = edges + calc(lv);
        }
        else
        {
            in_adj[lu].insert(v);
            edges = edges + calc(find_leader(lv));
            edges = edges + calc(find_leader(lu));
        }

        cout << edges << endl;
        //for (int j = 1; j <= n; j ++)
        //cout << "sz " << j << " " << sz[j] << endl;

    }
}

int main()
{
    solve();
    return 0;
}
/**
6 7
1 2
2 3
3 4
4 5
5 6
6 5
5 4

5 20
4 2
1 5
2 3
2 5
3 2
3 1
4 5
1 2
5 2
1 4
4 1
3 4
5 1
2 4
2 1
4 3
1 3
5 4
3 5
5 3


*/

Subtask #1
0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Incorrect 1 ms 604 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Incorrect 1 ms 604 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Incorrect 1 ms 604 KB Output isn't correct
4 Halted 0 ms 0 KB -