oj.uz

Submission #246514

# Submission time Handle Problem Language Result Execution time Memory
246514 2020-07-09T13:44:26 Z egekabas Making Friends on Joitter is Fun (JOI20_joitter2) C++14
1 / 100
 90 ms 10488 KB 
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll>    pll;
typedef pair<ull, ull>    pull;
typedef pair<int, int>  pii;
typedef pair<ld, ld>  pld;
ll ans = 0;
ll sq = 500;
ll n, m;
ll prt[100009];
ll sz[100009];
ll id[100009];
ll curbig = 1;
bitset<100009> comesto[509];
bitset<100009> bigin[509];
bitset<100009> bigout[509];
ll totin[100009];
vector<ll> in[100009];
vector<ll> out[100009];
bitset<100009> tmp;

ll findprt(ll x){
    if(prt[x] == x) return x;
    return prt[x] = findprt(prt[x]);
}
void makebig(ll x){
    id[x] = curbig++;
    for(auto u : in[x]){
        bigin[id[x]][findprt(u)] = 1;
        if(findprt(u) != x && comesto[id[x]][u] == 0){
            totin[x]++;
            comesto[id[x]][u] = 1;
        }
    }
    for(auto u : out[x])
        bigout[id[x]][findprt(u)] = 1;
}
ll calc(ll x){
    if(id[x]) return totin[x]*sz[x];
    ll cur = 0;
    for(auto u : in[x])
        if(findprt(u) != x && tmp[u] == 0){
            tmp[u] = 1;
            cur += sz[x];
        }
    for(auto u : in[x])
        tmp[u] = 0;
    return cur;
}
void merge(ll x, ll y){
    x = findprt(x);
    y = findprt(y);
    if(x == y) return;
    if(!id[x] && ll(in[x].size()+out[x].size()) > sq)
        makebig(x);
    if(!id[y] && ll(in[y].size()+out[y].size()) > sq)
        makebig(y);
    
    if(id[y] || (!id[x] && in[y].size()+out[y].size() > in[x].size()+out[x].size()))
        swap(x, y);
    
    if(id[x]){
        if(bigin[id[x]][y] == 0 || bigout[id[x]][y] == 0)
            return;
    }
    else{
        ll goin = 0;
        ll goout = 0;
        for(auto u : in[y])
            if(findprt(u) == x)++goin;
        for(auto u : out[y])
            if(findprt(u) == x)++goout;
        if(goin == 0 || goout == 0)
            return;
    }
    ans -= calc(x)+calc(y);
    vector<ll> mergelater;  
    if(id[x] && id[y]){
        totin[x] -= bigin[id[x]][y];
        prt[y] = x;
        bigout[id[x]] |= bigout[id[y]];
        bigin[id[x]] |= bigin[id[y]];
        comesto[id[x]] |= comesto[id[y]];
        totin[x] = 0;
        for(ll i = 1; i <= n; ++i){
            if(findprt(i) != x && comesto[id[x]][i])
                ++totin[x];
            if(findprt(i) == i && i != x && bigout[id[x]][i] && bigin[id[x]][i])
                mergelater.pb(i);
        }
        ans -= sz[x]*(sz[x]-1)+sz[y]*(sz[y]-1);
        sz[x] += sz[y];
        ans += sz[x]*(sz[x]-1);
    }
    else if(id[x]){
        prt[y] = x;
        for(auto u : in[y]){
            bigin[id[x]][findprt(u)] = 1;
            if(findprt(u) != x && comesto[id[x]][u] == 0){
                totin[x]++;
                comesto[id[x]][u] = 1;
            }
            if(findprt(u) != x && bigout[id[x]][findprt(u)])
                mergelater.pb(findprt(u));
        }
        for(auto u : out[y]){
            if(findprt(u) == x) totin[x]--;
            bigout[id[x]][findprt(u)] = 1;
            if(findprt(u) != x && bigin[id[x]][findprt(u)])
                mergelater.pb(findprt(u));
        }
        ans -= sz[x]*(sz[x]-1)+sz[y]*(sz[y]-1);
        sz[x] += sz[y];
        ans += sz[x]*(sz[x]-1);
    }
    else{
        prt[y] = x;
        for(auto u : in[y])
            if(findprt(u) != x) in[x].pb(u);
        for(auto u : out[y])
            if(findprt(u) != x) out[x].pb(u);
        ans -= sz[x]*(sz[x]-1)+sz[y]*(sz[y]-1);
        sz[x] += sz[y];
        ans += sz[x]*(sz[x]-1);
        for(auto u : in[x])
            tmp[findprt(u)] = 1;
        for(auto u : out[x])
            if(tmp[findprt(u)] && findprt(u) != x)
                mergelater.pb(findprt(u));
        for(auto u : in[x])
            tmp[findprt(u)] = 0;
    }
    for(ll i = 1; i < curbig; ++i){
        if(bigin[i][y])
            bigin[i][x] = bigin[i][y];
        bigin[i][y] = 0;
        if(bigout[i][y])
            bigout[i][x] = bigout[i][y];
        bigout[i][y] = 0; 
    }
    if(!id[x] && ll(in[x].size()+out[x].size()) > sq)
        makebig(x);
    ans += calc(x);
    for(auto u : mergelater){
        merge(x, u);
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);

    //freopen("in.txt", "r", stdin);                                                                                             
    //freopen("out.txt", "w", stdout);

    cin >> n >> m;
    for(ll i = 1; i <= n; ++i){
        sz[i] = 1;
        prt[i] = i;
    }
    while(m--){
        ll x, y;
        cin >> x >> y;
        ll dont = (findprt(x) == findprt(y));
        if(id[findprt(y)]){
            if(comesto[id[findprt(y)]][x])
                dont = 1;
            else
                totin[findprt(y)]++;
            comesto[id[findprt(y)]][x] = 1;    
        }
        else{
            for(auto u : in[findprt(y)])
                if(u == x)
                    dont = 1;
        }
        if(dont){
            cout << ans << '\n';
            continue;
        }
        if(id[findprt(x)] == 0)
            out[findprt(x)].pb(y);
        if(id[findprt(y)] == 0)
            in[findprt(y)].pb(x);
        x = findprt(x);
        y = findprt(y);
        ans += sz[y];
        if(id[x])
            bigout[id[x]][y] = 1;
        if(id[y])
            bigin[id[y]][x] = 1;
        
        merge(x, y);
        
        cout << ans << '\n';
    }
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4992 KB Output is correct
2 Correct 7 ms 4992 KB Output is correct
3 Correct 8 ms 5120 KB Output is correct
4 Correct 7 ms 4992 KB Output is correct
5 Correct 7 ms 5120 KB Output is correct
6 Correct 8 ms 5120 KB Output is correct
7 Correct 8 ms 4992 KB Output is correct
8 Correct 8 ms 5120 KB Output is correct
9 Correct 11 ms 5120 KB Output is correct
10 Correct 8 ms 5120 KB Output is correct
11 Correct 7 ms 5120 KB Output is correct
12 Correct 8 ms 5120 KB Output is correct
13 Correct 7 ms 4992 KB Output is correct
14 Correct 9 ms 4992 KB Output is correct
15 Correct 7 ms 5120 KB Output is correct
16 Correct 7 ms 5120 KB Output is correct
17 Correct 7 ms 4992 KB Output is correct
18 Correct 7 ms 4992 KB Output is correct
19 Correct 8 ms 4992 KB Output is correct
20 Correct 8 ms 5120 KB Output is correct
21 Correct 8 ms 5120 KB Output is correct
22 Correct 8 ms 4992 KB Output is correct
23 Correct 8 ms 5120 KB Output is correct
24 Correct 7 ms 5120 KB Output is correct
25 Correct 11 ms 5120 KB Output is correct
26 Correct 9 ms 5120 KB Output is correct
27 Correct 9 ms 5120 KB Output is correct
28 Correct 7 ms 5120 KB Output is correct
29 Correct 8 ms 5120 KB Output is correct
30 Correct 7 ms 4992 KB Output is correct
31 Correct 8 ms 5120 KB Output is correct
32 Correct 7 ms 5120 KB Output is correct
33 Correct 8 ms 5120 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4992 KB Output is correct
2 Correct 7 ms 4992 KB Output is correct
3 Correct 8 ms 5120 KB Output is correct
4 Correct 7 ms 4992 KB Output is correct
5 Correct 7 ms 5120 KB Output is correct
6 Correct 8 ms 5120 KB Output is correct
7 Correct 8 ms 4992 KB Output is correct
8 Correct 8 ms 5120 KB Output is correct
9 Correct 11 ms 5120 KB Output is correct
10 Correct 8 ms 5120 KB Output is correct
11 Correct 7 ms 5120 KB Output is correct
12 Correct 8 ms 5120 KB Output is correct
13 Correct 7 ms 4992 KB Output is correct
14 Correct 9 ms 4992 KB Output is correct
15 Correct 7 ms 5120 KB Output is correct
16 Correct 7 ms 5120 KB Output is correct
17 Correct 7 ms 4992 KB Output is correct
18 Correct 7 ms 4992 KB Output is correct
19 Correct 8 ms 4992 KB Output is correct
20 Correct 8 ms 5120 KB Output is correct
21 Correct 8 ms 5120 KB Output is correct
22 Correct 8 ms 4992 KB Output is correct
23 Correct 8 ms 5120 KB Output is correct
24 Correct 7 ms 5120 KB Output is correct
25 Correct 11 ms 5120 KB Output is correct
26 Correct 9 ms 5120 KB Output is correct
27 Correct 9 ms 5120 KB Output is correct
28 Correct 7 ms 5120 KB Output is correct
29 Correct 8 ms 5120 KB Output is correct
30 Correct 7 ms 4992 KB Output is correct
31 Correct 8 ms 5120 KB Output is correct
32 Correct 7 ms 5120 KB Output is correct
33 Correct 8 ms 5120 KB Output is correct
34 Correct 11 ms 5248 KB Output is correct
35 Incorrect 90 ms 10488 KB Output isn't correct
36 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4992 KB Output is correct
2 Correct 7 ms 4992 KB Output is correct
3 Correct 8 ms 5120 KB Output is correct
4 Correct 7 ms 4992 KB Output is correct
5 Correct 7 ms 5120 KB Output is correct
6 Correct 8 ms 5120 KB Output is correct
7 Correct 8 ms 4992 KB Output is correct
8 Correct 8 ms 5120 KB Output is correct
9 Correct 11 ms 5120 KB Output is correct
10 Correct 8 ms 5120 KB Output is correct
11 Correct 7 ms 5120 KB Output is correct
12 Correct 8 ms 5120 KB Output is correct
13 Correct 7 ms 4992 KB Output is correct
14 Correct 9 ms 4992 KB Output is correct
15 Correct 7 ms 5120 KB Output is correct
16 Correct 7 ms 5120 KB Output is correct
17 Correct 7 ms 4992 KB Output is correct
18 Correct 7 ms 4992 KB Output is correct
19 Correct 8 ms 4992 KB Output is correct
20 Correct 8 ms 5120 KB Output is correct
21 Correct 8 ms 5120 KB Output is correct
22 Correct 8 ms 4992 KB Output is correct
23 Correct 8 ms 5120 KB Output is correct
24 Correct 7 ms 5120 KB Output is correct
25 Correct 11 ms 5120 KB Output is correct
26 Correct 9 ms 5120 KB Output is correct
27 Correct 9 ms 5120 KB Output is correct
28 Correct 7 ms 5120 KB Output is correct
29 Correct 8 ms 5120 KB Output is correct
30 Correct 7 ms 4992 KB Output is correct
31 Correct 8 ms 5120 KB Output is correct
32 Correct 7 ms 5120 KB Output is correct
33 Correct 8 ms 5120 KB Output is correct
34 Correct 11 ms 5248 KB Output is correct
35 Incorrect 90 ms 10488 KB Output isn't correct
36 Halted 0 ms 0 KB -