oj.uz

답안 #734100

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
734100 2023-05-01T16:44:36 Z mosiashvililuka 조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2) C++14
0 / 100
 12 ms 21460 KB 
#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,pas,t,tes,msh[100009];
map <long long, bool> mp[100009];
map <long long, vector <long long> > M[100009];
vector <long long> V[100009];
multiset <long long> in[100009],out[100009];
multiset <long long>::iterator it,tt;
bool check(long long q, long long w){
    multiset <long long>::iterator it;
    it=out[w].lower_bound(q);
    if(it==out[w].end()||(*it)!=q) return 0; else return 1;
}
void ADD(long long q, long long w){
    long long Q=q,W=w;
    q=msh[q];w=msh[w];
    if(q==w) return;
    if(check(q,w)==0){
        if(mp[Q][w]==0){
            out[q].insert(w);
            in[w].insert(q);
            pas+=V[w].size();
            mp[Q][w]=1;
            M[q][w].push_back(Q);
        }
        return;
    }
    if(V[q].size()+in[q].size()+out[q].size()<V[w].size()+in[w].size()+out[w].size()) swap(q,w);//shedareba sadac kidev unda daamato wevrebi(sizes)
    //
    vector <pair <long long, long long> > NXT;
    long long shida=0;
    for(it=in[w].begin(); it!=in[w].end(); it++){
        if((*it)==q){
            pas-=V[w].size();
            tt=out[q].lower_bound(w);
            out[q].erase(tt);
            continue;
        }
        //
        c=M[(*it)][w].back();
        M[(*it)][w].pop_back();
        mp[c][q]=1;
        //
        if(check((*it),q)==1) NXT.push_back({(*it),q});
        pas+=V[q].size();
        tt=out[(*it)].lower_bound(w);
        out[(*it)].erase(tt);
        out[(*it)].insert(q);
        in[q].insert((*it));
    }
    for(it=out[w].begin(); it!=out[w].end(); it++){
        if((*it)==q){
            pas-=V[q].size();shida++;
            tt=in[q].lower_bound(w);
            in[q].erase(tt);
            continue;
        }
        if(check(q,(*it))==1) NXT.push_back({q,(*it)});
        tt=in[(*it)].lower_bound(w);
        in[(*it)].erase(tt);
        in[(*it)].insert(q);
        out[q].insert((*it));
    }
    long long qw=in[q].size(),we=V[w].size();
    pas+=(qw-shida)*we;
    //
    in[w].clear();out[w].clear();
    pas-=V[q].size()*(V[q].size()-1);
    pas-=V[w].size()*(V[w].size()-1);
    for(vector <long long>::iterator ITT=V[w].begin(); ITT!=V[w].end(); ITT++){
        V[q].push_back((*ITT));msh[(*ITT)]=q;
    }
    pas+=V[q].size()*(V[q].size()-1);
    V[w].clear();
    while(NXT.size()){
        ADD(NXT.back().first,NXT.back().second);
        //cout<<q<<" "<<w<<"   "<<NXT.back().first<<" "<<NXT.back().second<<"\n";
        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;
        ADD(c,d);
        cout<<pas<<"\n";
    }
    return 0;
}

Compilation message

joitter2.cpp: In function 'void ADD(long long int, long long int)':
joitter2.cpp:15:19: warning: unused variable 'W' [-Wunused-variable]
   15 |     long long Q=q,W=w;
      |                   ^

Subtask #1
0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 21460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 21460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 21460 KB Output isn't correct
2 Halted 0 ms 0 KB -