제출 #838291

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
838291		idiotcomputer	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++11	0 / 100	6 ms	9748 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() && (*it).first == a){
        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() && (*it).first == a){
        auto it2 = it;
        it++;
        ain[b].erase(it2);
    }
    
    res -= ssize[b] * (long long int) ain[b].size();
    
    int ca = -1;
    //cout << "HRERE2\n";
    for (auto it = aout[a].begin(); it != aout[a].end(); it++){
        int next = (*it).first;
        if (next == b){
            res -= ssize[b];
            continue;
        }
        auto it2 = ain[next].lower_bound({a,-1});
        while (it2 != ain[next].end() && (*it2).first == a){
            ain[next].insert({b,(*it2).second});
            auto it3 = it2;
            it2++;
            ain[next].erase(it3);
        }
        if (ca == -1){
            it2 = aout[(*it).first].lower_bound({b,-1});
            if (it2 != aout[(*it).first].end() && (*it2).first == b){
                ca = (*it).first;
            }
        }
        aout[b].insert((*it));
    }
    
  //  cout<< "HERERER3\n";
    
    for (auto it = ain[a].begin(); it != ain[a].end(); it++){
        int next = (*it).first;
        if (next == b){
            continue;
        }
        auto it2 = aout[next].lower_bound({a,-1});
        while (it2 != aout[next].end() && (*it2).first == a){
            aout[next].insert({b,(*it2).second});
            auto it3 = it2;
            it2++;
            aout[next].erase(it3);
        }
        res -= ssize[a];
        ain[b].insert(*it);
        
        if (ca == -1){
            it2 = ain[next].lower_bound({b,-1});
            if (it2 != ain[next].end() && (*it2).first == b){
                ca = next;
            }
        }
    }
  //  cout << "H4\n";
    p[a] = b;
    ssize[b] += ssize[a];
    
    
    res += ssize[b] * (long long int) ain[b].size();
  //  cout << a << "," << b << ": " << res << " ... " << ca << '\n';
    if (ca != -1){
        comb(ca,b);
    }
        
}
 
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