oj.uz

답안 #383255

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
383255 2021-03-29T11:05:54 Z VodkaInTheJar 조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2) C++14
0 / 100
 1 ms 364 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define endl '\n'

using namespace std;

const int maxn = 1e5 + 3; 

int par[maxn], sz[maxn];
int find_root(int ver)
{
    if (ver == par[ver])
        return ver;

    return par[ver] = find_root(par[ver]);
}

void merge(int a, int b)
{
    a = find_root(a), b = find_root(b);
    if (sz[a] < sz[b])
        swap(a, b);

    sz[a] += sz[b];
    par[b] = a;
}

int n, m; 
void read()
{
	cin >> n >> m; 
}

vector <pair <int, int> > v; 

long long find_ans()
{
    long long ans = 0;
    for (int i = 1; i <= n; i++)
        if (i == par[i])
            ans += 1ll * sz[i] * (sz[i] - 1);

    set <pair <int, int> > s; 
    for (auto i: v)
    {
        int a = find_root(i.first), b = find_root(i.second);
        if (a == b)
            continue;

        if (s.find({i.first, b}) != s.end())
            continue;

        ans += sz[b];
        s.insert({i.first, b});
    }

    return ans; 
}

void solve()
{
	for (int i = 1; i <= n; i++)
        par[i] = i, sz[i] = 1;

    for (int i = 1; i <= m; i++)
    {
        int a, b;
        cin >> a >> b;

        v.push_back({a, b});

        bool is = false;
        for (auto j: v)
            if (j.first == b && j.second == a)
            {
                is = true;
                break;
            }

        if (is)
        merge(a, b);

        cout << find_ans() << endl; 
    }
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	
	read();
	solve();
}

Subtask #1
0 / 1.0

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

Subtask #2
0 / 16.0

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

Subtask #3
0 / 83.0

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