oj.uz

Submission #384083

# Submission time Handle Problem Language Result Execution time Memory
384083 2021-03-31T11:54:44 Z VodkaInTheJar Making Friends on Joitter is Fun (JOI20_joitter2) C++14
0 / 100
 12 ms 14444 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];
set <int> adj[maxn], rev_adj[maxn], members[maxn];

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

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

long long ans = 0; 
void merge(int a, int b)
{
    a = find_root(a), b = find_root(b);
    
    if (a == b)
        return;

    ans -= 1ll * sz[a] * (sz[a] - 1);
    ans -= 1ll * sz[b] * (sz[b] - 1);
    ans -= 1ll * (int)rev_adj[a].size() * sz[a];
    ans -= 1ll * (int)rev_adj[b].size() * sz[b];

    for (auto i: members[b])
        members[a].insert(i);

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

    for (auto j: adj[b])
        if (j != a)
        adj[a].insert(j);

    for (auto j: rev_adj[b])
    {
        if (find_root(j) == a)
            continue;

        adj[find_root(j)].erase(b);
        adj[find_root(j)].insert(a);
        rev_adj[a].insert(j);
    }
    
    adj[a].erase(b);
    vector <int> to_remove;
    for (auto i: members[b])
        if (rev_adj[a].find(i) != rev_adj[a].end())
            to_remove.push_back(i);

    for (auto i: to_remove)
        rev_adj[a].erase(i);
    
    /*
    cout << a << ":";
    for (auto i: adj[a])
        cout << i << " ";

    cout << endl;
    cout << endl;
    for (auto i: rev_adj[a])
        cout << i << " ";
 //   cout << endl;
   // cout << rev_adj[1].size() << endl; 
  //  cout << endl;
    exit(0);
    */


    par[b] = a;
    sz[a] += sz[b];
    ans += 1ll * sz[a] * (sz[a] - 1);
    ans += 1ll * (int)rev_adj[a].size() * sz[a];
}

pair <int, int> e[maxn * 3];
void solve()
{
    for (int i = 1; i <= n; i++)
    {
        par[i] = i, sz[i] = 1; 
        members[i].insert(i);
    }

    for (int i = 1; i <= m; i++)
    {
        cin >> e[i].first >> e[i].second;
        
        int a = find_root(e[i].first), b = find_root(e[i].second);
        if (a != b)
        {
            ans -= 1ll * (int)rev_adj[b].size() * sz[b]; 
            adj[a].insert(b);
            rev_adj[b].insert(e[i].first);

            ans += 1ll * (int)rev_adj[b].size() * sz[b];

            int curr = a;
            for (;;)
            {
                bool can = false;
                for (auto j: adj[curr])
                    if (adj[j].find(curr) != adj[j].end())
                    {
                        merge(j, curr);
                        curr = find_root(curr);
                        can = true;
                        break;
                    }

                if (!can)
                    break;
            }
        }

        //cout << i << "shit" << (int)rev_adj[2].size() << endl;
       // cout << find_ans(i) << endl; 
       cout << ans << 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 11 ms 14444 KB Output is correct
2 Correct 12 ms 14444 KB Output is correct
3 Correct 11 ms 14444 KB Output is correct
4 Correct 12 ms 14444 KB Output is correct
5 Correct 11 ms 14444 KB Output is correct
6 Correct 10 ms 14444 KB Output is correct
7 Correct 11 ms 14444 KB Output is correct
8 Incorrect 11 ms 14444 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14444 KB Output is correct
2 Correct 12 ms 14444 KB Output is correct
3 Correct 11 ms 14444 KB Output is correct
4 Correct 12 ms 14444 KB Output is correct
5 Correct 11 ms 14444 KB Output is correct
6 Correct 10 ms 14444 KB Output is correct
7 Correct 11 ms 14444 KB Output is correct
8 Incorrect 11 ms 14444 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14444 KB Output is correct
2 Correct 12 ms 14444 KB Output is correct
3 Correct 11 ms 14444 KB Output is correct
4 Correct 12 ms 14444 KB Output is correct
5 Correct 11 ms 14444 KB Output is correct
6 Correct 10 ms 14444 KB Output is correct
7 Correct 11 ms 14444 KB Output is correct
8 Incorrect 11 ms 14444 KB Output isn't correct
9 Halted 0 ms 0 KB -