oj.uz

Submission #605221

# Submission time Handle Problem Language Result Execution time Memory
605221 2022-07-25T14:12:42 Z DJeniUp Making Friends on Joitter is Fun (JOI20_joitter2) C++17
0 / 100
 9 ms 19056 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll,ll>pairll;
typedef pair<ll,pairll>pairlll;
typedef unsigned long long ull;
typedef long double ld;

#define fr first
#define sc second
#define pb push_back
#define INF 1000000007
#define N 200007
#define endl '\n'

ll n,M,f[100007],res,sz[100007],a[100007];

set<ll>s[100007],p[100007],d[100007];
set<ll>k;

map<ll,ll>m[100007];

ll P(ll x){
    if(f[x]!=x)f[x]=P(f[f[x]]);
    return f[x];
}

void A(ll x,ll y){
    if(p[x].size()<p[y].size()){
        swap(x,y);
    }
    //cout<<x<<" "<<y<<" "<<a[x]<<" "<<a[y]<<" "<<sz[x]<<" "<<sz[y]<<endl;
    res-=a[x]*sz[x];
    res-=a[y]*sz[y];
    res-=sz[x]*(sz[x]-1);
    res-=sz[y]*(sz[y]-1);
    sz[x]+=sz[y];
    res+=sz[x]*(sz[x]-1);
    for(auto it:s[y]){
        if(P(it)!=x){
            s[x].insert(P(it));
        }
    }
    k.clear();
    a[x]=0;
    for(auto it:p[x]){
        if(P(it)!=x && P(it)!=y){
            a[x]++;
            k.insert(it);
        }
    }
    swap(p[x],k);
    for(auto it:p[y]){
        if(p[x].count(it)==0 && P(it)!=x && P(it)!=y){
            a[x]++;
            p[x].insert(it);
        }
    }
    for(auto it:d[y]){
        if(P(it)!=x){
            s[P(it)].insert(x);
            d[x].insert(P(it));
        }
    }
    res+=a[x]*sz[x];
    f[y]=x;
    return ;
}

int main()
{
    cin>>n>>M;
    for(int i=1;i<=n;i++){
        f[i]=i;
        sz[i]=1;
    }
    for(int i=1;i<=M;i++){
        ll x,y;
        cin>>x>>y;
        if(P(x)!=P(y)){
            //cout<<P(y)<<" "<<P(x)<<" "<<s[P(x)].count(P(y))<<endl;
            ll fl=0;
            for(auto it:s[P(x)]){
                if(P(it)==P(y)){
                    fl=1;
                    break;
                }
            }
            if(fl==1)A(P(x),P(y));
            else{
                if(p[P(y)].count(x)==0){
                    res+=sz[P(y)];
                    p[P(y)].insert(x);
                    a[P(y)]++;
                }
                m[P(x)][P(y)]++;
                s[P(y)].insert(P(x));
                d[P(x)].insert(P(y));
            }
        }
        cout<<res<<endl;

    }

    return 0;
}

Subtask #1
0 / 1.0

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

Subtask #2
0 / 16.0

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

Subtask #3
0 / 83.0

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