oj.uz

Submission #384066

# Submission time Handle Problem Language Result Execution time Memory
384066 2021-03-31T10:20:38 Z VodkaInTheJar Making Friends on Joitter is Fun (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 n, m; 
void read()
{
	cin >> n >> m; 
}

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

    return find_root(par[ver]);
}

void merge(int a, int b)
{
    
    a = find_root(a), b = find_root(b);
    
    /*
    if (a == b)
        return;

    if (sz[a] < sz[b])
        swap(a, b);

    par[b] = a;
    sz[a] += sz[b];
    */

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

pair <int, int> e[maxn * 3];
long long find_ans(int idx)
{
    long long ans = 0; 
    for (int i = 1; i <= n; i++)
        if (i == find_root(i))
            ans += 1ll * sz[i] * (sz[i] - 1); 


    set <pair <int, int> > s; 
    for (int i = 1; i <= idx; i++)
        if (find_root(e[i].first) != find_root(e[i].second))
        {
            s.insert({e[i].first, find_root(e[i].second)});
            //ans += sz[find_root(e[i].second)];
        }

    for (auto i: s)
        ans += sz[i.second];

    return ans; 
}

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

    for (int i = 1; i <= m; i++)
    {
        cin >> e[i].first >> e[i].second;
        
        if (find_root(e[i].first) != find_root(e[i].second))
        {
            for (int j = 1; j <= i-1; j++)
                if (find_root(e[j].second) == find_root(e[i].first) && find_root(e[j].first) == find_root(e[i].second))
                { 
                    merge(e[i].first, e[i].second);
                    break;
                }
        }

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

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

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Incorrect 1 ms 364 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Incorrect 1 ms 364 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Incorrect 1 ms 364 KB Output isn't correct
4 Halted 0 ms 0 KB -