제출 #835627

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
835627		idiotcomputer	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++11	0 / 100	4 ms	9684 KiB

joitter2

#include <bits/stdc++.h>
using namespace std;

const int mxN = 1e5;
int p[mxN];
int ssize[mxN];
vector<set<pair<int,int>>> ain(mxN);
vector<set<pair<int,int>>> aout(mxN);

long long int res = 0;

void upd(int a){
    while (p[p[a]] != p[a]){
        p[a] = p[p[a]];
    }
}

void comb(int a, int b){
    if (ssize[a] > ssize[b]){
        swap(a,b);
    }
    res += (long long int) ssize[a] * ssize[b]*2;
    
   /* cout << a <<';' << b << ' ' << res << ' ' << ssize[a] << " " << ssize[b] << '\n';
    cout << "a: ";
    for (auto it = aout[a].begin(); it != aout[a].end(); it++){
        cout << (*it).first << "," << (*it).second << " ";
    } 
    cout << '\n';
    for (auto it = ain[a].begin(); it != ain[a].end(); it++){
        cout << (*it).first << "," << (*it).second << ' ';
    }
    cout << '\n';
    cout << "b: \n";
     for (auto it = aout[b].begin(); it != aout[b].end(); it++){
        cout << (*it).first << "," << (*it).second << " ";
    }
    cout << '\n';
    for (auto it = ain[b].begin(); it != ain[b].end(); it++){
        cout << (*it).first << "," << (*it).second << " ";
    }
    cout << "\n\n";*/
    auto it = aout[b].lower_bound({a,-1});
    while (it != aout[b].end()){
        upd((*it).first);
        if (p[(*it).first] != a){
            break;
        }
        res -= ssize[a];
        auto it2 = it;
        it++;
        aout[b].erase(it2);
    }
   // cout << "HRE\n";
    
    it = ain[b].lower_bound({a,-1});
    while (it != ain[b].end()){
        upd((*it).first);
        if (p[(*it).first] != a){
            break;
        }
        auto it2 = it;
        it++;
        ain[b].erase(it2);
    }
    
    res -= ssize[b] * (long long int) ain[b].size();
    
    //cout << "HRERE2\n";
    for (auto it = aout[a].begin(); it != aout[a].end(); it++){
        upd((*it).first);
        if (p[(*it).first] == b){
            res -= ssize[b];
            continue;
        }
        aout[b].insert({p[(*it).first],(*it).second});
    }
    
  //  cout<< "HERERER3\n";
    
    for (auto it = ain[a].begin(); it != ain[a].end(); it++){
        upd((*it).first);
        if (p[(*it).first] == b){
            continue;
        }
        res -= ssize[a];
        ain[b].insert({p[(*it).first],(*it).second});
    }
  //  cout << "H4\n";
    p[a] = b;
    ssize[b] += ssize[a];
    
    
    res += ssize[b] * (long long int) ain[b].size();
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n,m;
    cin >> n >> m;
    
    for (int i =0; i < n; i++){
        p[i] = i;
        ssize[i] = 1;
    }
    
    int a,b;
    for (int i = 0; i < m; i++){
        cin >> a >> b;
        a -= 1;
        b -= 1;
        upd(a);
        upd(b);
        if (p[a] == p[b]){
            cout << res << '\n';
            continue;
        }
        
        auto it = aout[p[a]].find({p[b],a});
        if (it != aout[p[a]].end()){
            cout << res << '\n';
            continue;
        }
      //  cout << "TEMp " << res << '\n';
        res += ssize[p[b]];
        aout[p[a]].insert({p[b],a});
        ain[p[b]].insert({p[a],a});
        
        it = ain[p[a]].lower_bound({p[b],-1});
        if (it != ain[p[a]].end() && (*it).first == p[b]){
            comb(p[a],p[b]);
        }
        
        cout << res << '\n';
    }
    return 0;
}

• Subtask 1: 0 / 1
• Subtask 2: 0 / 16
• Subtask 3: 0 / 83