oj.uz

Submission #734273

# Submission time Handle Problem Language Result Execution time Memory
734273 2023-05-02T08:08:07 Z mosiashvililuka Making Friends on Joitter is Fun (JOI20_joitter2) C++14
0 / 100
 5000 ms 16732 KB 
#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,t,tes,msh[100009],pas,C,D;
vector <long long> V[100009];
set <long long> in[100009],out[100009],sm[100009];//sm-c ideashi in-ebia ogond komponentis magivrad wveros nomers agdeb
set <long long>::iterator it,tt;
bool check(long long q, long long w){
    if(out[w].find(q)==out[w].end()) return 0; else return 1;
}
void mrg(long long Q, long long W){
    long long q=msh[Q],w=msh[W];
    if(q==w) return;
    if(V[q].size()<V[w].size()) swap(q,w);
    long long qw=V[q].size(),we=V[w].size(),Sq=sm[q].size(),Sw=sm[w].size();
    pas-=qw*(qw-1);
    pas-=we*(we-1);
    pas-=qw*Sq;
    pas-=we*Sw;
    //
    vector <pair <long long, long long> > NXT;
    for(vector <long long>::iterator IT=V[w].begin(); IT!=V[w].end(); IT++){
        V[q].push_back((*IT));
        tt=sm[q].find((*IT));
        if(tt!=sm[q].end()){
            sm[q].erase(tt);
        }
        msh[(*IT)]=q;
    }
    V[w].clear();
    for(it=sm[w].begin(); it!=sm[w].end(); it++){
        if(msh[(*it)]==q) continue;
        if(sm[q].find((*it))==sm[q].end()){
            sm[q].insert((*it));
        }
    }
    Sq=sm[q].size();
    pas+=(qw+we)*Sq;
    //
    for(it=in[w].begin(); it!=in[w].end(); it++){
        if((*it)==q) continue;
        out[(*it)].erase(out[(*it)].find(w));
        out[(*it)].insert(q);
        in[q].insert((*it));
        if(check((*it),q)) NXT.push_back({(*it),q});
    }
    for(it=out[w].begin(); it!=out[w].end(); it++){
        if((*it)==q) continue;
        in[(*it)].erase(in[(*it)].find(w));
        in[(*it)].insert(q);
        out[q].insert((*it));
        if(check(q,(*it))) NXT.push_back({(*it),q});
    }
    //
    in[w].clear();out[w].clear();sm[w].clear();
    pas+=V[q].size()*(V[q].size()-1);
    while(NXT.size()){
        mrg(NXT.back().first,NXT.back().second);
        NXT.pop_back();
    }
}
int main(){
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>a>>tes;
    for(i=1; i<=a; i++){
        msh[i]=i;V[i].push_back(i);
    }
    for(t=1; t<=tes; t++){
        cin>>C>>D;
        c=msh[C],d=msh[D];
        if(c==d){
            cout<<pas<<"\n";
            continue;
        }
        if(check(c,d)==0){
            if(sm[d].find(C)!=sm[d].end()){
                cout<<pas<<"\n";
                continue;
            }
            pas+=V[d].size();
            in[d].insert(c);out[c].insert(d);
            sm[d].insert(C);
            cout<<pas<<"\n";
            continue;
        }
        in[d].insert(c);out[c].insert(d);
        sm[d].insert(C);
        pas+=V[d].size();
        mrg(c,d);
        cout<<pas<<"\n";
    }
    return 0;
}

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16724 KB Output is correct
2 Correct 8 ms 16652 KB Output is correct
3 Correct 8 ms 16732 KB Output is correct
4 Correct 8 ms 16724 KB Output is correct
5 Execution timed out 5053 ms 16720 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16724 KB Output is correct
2 Correct 8 ms 16652 KB Output is correct
3 Correct 8 ms 16732 KB Output is correct
4 Correct 8 ms 16724 KB Output is correct
5 Execution timed out 5053 ms 16720 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16724 KB Output is correct
2 Correct 8 ms 16652 KB Output is correct
3 Correct 8 ms 16732 KB Output is correct
4 Correct 8 ms 16724 KB Output is correct
5 Execution timed out 5053 ms 16720 KB Time limit exceeded
6 Halted 0 ms 0 KB -