Submission #961820

#	Time	Username	Problem	Language	Result	Execution time	Memory
961820		danikoynov	Making Friends on Joitter is Fun (JOI20_joitter2)	C++14	100 / 100	1423 ms	83252 KiB

joitter2

#include <bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

const int maxn = 2e5 + 10;

int n, par[maxn], m;
int sz[maxn];

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


set < int > rem;
set < int > adj[maxn];
set < int > rev_adj[maxn], child[maxn];
ll ans;

queue < pair < int, int > > to_merge;

void insert_weak_connection(int a, int b)
{
     adj[a].insert(b);
     rev_adj[b].insert(a);

     if (adj[b].count(a))
     to_merge.push({a, b});
}
void unite(int v, int u)
{
     if (v == u)
          return;

     if (child[v].size() < child[u].size())
          swap(v, u);

     ans = ans + (ll)(child[v].size()) * sz[u] + (ll)(child[u].size()) * sz[v];


     par[u] = v;
     sz[v] += sz[u];

     for (int d : child[u])
     {
          if (child[v].count(d)) ans -= sz[v];
          else
               child[v].insert(d);
     }

     adj[v].erase(u);
     adj[u].erase(v);
     rev_adj[v].erase(u);
     rev_adj[u].erase(v);

     for (int d : adj[u])
     {
          rev_adj[d].erase(u);
          insert_weak_connection(v, d);
     }

     for (int d : rev_adj[u])
     {
          adj[d].erase(u);
          insert_weak_connection(d, v);
     }



}
void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++)
    {
        par[i] = i;
        sz[i] = 1;
          child[i].insert(i);
    }

    for (int i = 1; i <= m; i ++)
    {
        int v, u;
        cin >> v >> u;
        u = find_leader(u);
        if (find_leader(v) != u && !child[u].count(v))
        {
             child[u].insert(v);
             ans += sz[u];

             v = find_leader(v);
             insert_weak_connection(v, u);

             while(to_merge.size())
             {
                    pair < int, int > cur = to_merge.front();
                    to_merge.pop();
                    unite(find_leader(cur.first), find_leader(cur.second));
             }
        }

        cout << ans << endl;

    }
}

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

10 18
10 6
7 8
8 4
9 3
2 8
9 2
1 10
1 8
8 9
5 6

2 10
4 3
7 2
10 2
10 5
3 7
1 9
8 7

1 2
9 1
7 6
9 7
10 3
8 3
6 3
7 5
8 2
6 1
4 9
7 1
4 2
6 8
7 3
9 8
5 1
10 4
6 4
1 4
6 7
3 1
9 10
3 2
1 7
2 5
10 1
2 7
2 1
5 8
7 9
2 4
6 9
3 8
10 7
8 5
5 4
8 6
5 10
3 5
5 7
8 1
4 7
4 1
10 8
9 5
4 8
6 10
1 6
2 9
1 5
6 5
3 9
4 10
2 3
5 2
1 3
4 6
2 6
8 10
3 10
4 5
3 6
9 4
5 3
9 6
6 2
7 10
3 4
5 9
10 9
7 4


*/

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