oj.uz

Submission #1020617

# Submission time Handle Problem Language Result Execution time Memory
1020617 2024-07-12T07:41:05 Z _shr104 Making Friends on Joitter is Fun (JOI20_joitter2) C++14
0 / 100
 12 ms 14476 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define pb push_back
#define pf push_front
#define fi first
#define se second
const ll mod = 1e9+7, mxn = 1e5+7;
vector<set<ll>> g(mxn), rg(mxn), c(mxn);
queue<pair<ll,ll>> full_edge;
ll pr[mxn], n, m, cnt = 0, sz[mxn];
ll fs(ll u) 
{
    if (u == pr[u]) return u;
    return pr[u] = fs(pr[u]);
}
void add(ll u, ll v) // u and v = set
{
    g[u].insert(v); rg[v].insert(u);
    if (g[v].count(u)) full_edge.push({u,v});
}   
ll gsz(ll u) {return c[u].size()+g[u].size()+rg[u].size();} // u = set
void us(ll u, ll v)
{
    if (gsz(u) < gsz(v)) swap(u, v);
    cnt += sz[u]*c[v].size()+sz[v]*c[u].size();
    pr[v] = u; sz[u] += sz[v];
    for (ll i : c[v]) 
    {
        if (c[u].count(i)) cnt -= sz[u];
        else c[u].insert(i);
    }
    g[u].erase(v); rg[v].erase(u);
    g[v].erase(u); rg[u].erase(v);
    for (ll i : g[v])
    {
        rg[i].erase(v);
        add(u,i);
    }
    for (ll i : rg[v])
    {
        g[i].erase(v);
        add(i,u);
    }
}
signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    // freopen("test.inp","r",stdin); freopen("test.out","w",stdout); freopen("test.err","w",stderr);
    cin >> n >> m;
    for (ll i = 1; i <= n; i++) {pr[i] = i; sz[i] = 1; c[i].insert(i);}
    while (m--)
    {
        ll u, v; cin >> u >> v;
        v = fs(v);
        if (fs(u) != v && !c[v].count(u))
        {
            c[v].insert(u);
            cnt += sz[v];
            u = fs(u);
            add(u,v);
            while (full_edge.size()) 
            {
                pair<ll,ll> i = full_edge.front();
                full_edge.pop();
                us(fs(i.fi),fs(i.se));
            }
        }
        cout << cnt << '\n';
    }
}

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14428 KB Output is correct
2 Correct 7 ms 14428 KB Output is correct
3 Correct 6 ms 14424 KB Output is correct
4 Correct 6 ms 14428 KB Output is correct
5 Correct 6 ms 14336 KB Output is correct
6 Correct 6 ms 14424 KB Output is correct
7 Incorrect 12 ms 14476 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14428 KB Output is correct
2 Correct 7 ms 14428 KB Output is correct
3 Correct 6 ms 14424 KB Output is correct
4 Correct 6 ms 14428 KB Output is correct
5 Correct 6 ms 14336 KB Output is correct
6 Correct 6 ms 14424 KB Output is correct
7 Incorrect 12 ms 14476 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14428 KB Output is correct
2 Correct 7 ms 14428 KB Output is correct
3 Correct 6 ms 14424 KB Output is correct
4 Correct 6 ms 14428 KB Output is correct
5 Correct 6 ms 14336 KB Output is correct
6 Correct 6 ms 14424 KB Output is correct
7 Incorrect 12 ms 14476 KB Output isn't correct
8 Halted 0 ms 0 KB -