Submission #821293

#	Time	Username	Problem	Language	Result	Execution time	Memory
821293		vnm06	Marshmallow Molecules (CCO19_day2problem2)	C++14	25 / 25	117 ms	33888 KiB

Main

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;

int n, q;
pair<int, int> a[100005];
int brr=0;
int loc[100005];
int par[100005], db[100005];
vector<int> rd[100005];
vector<int> gr[100005];
int lb[100005];
set<int> st[100005];
long long sm[100005];

int main()
{
    ///ios::sync_with_stdio(0);
    ///cin.tie(0);
    ///cout.tie(0);

    cin>>n>>q;
    for(int i=0; i<q; i++)
    {
        cin>>a[i].first>>a[i].second;
    }
    sort(a, a+q);
    for(int i=0; i<q; i++)
    {
        int j=i;
        rd[a[i].first].push_back(brr);
        rd[a[i].second].push_back(brr);
        st[a[i].first].insert(a[i].second);
        while(j<q-1 && a[j+1].first==a[i].first) {j++; rd[a[j].second].push_back(brr); st[a[i].first].insert(a[j].second);}
        db[brr]=1;
        lb[brr]=a[i].first;
        par[brr]=brr;
        brr++;
        i=j;
    }
    for(int i=1; i<=n; i++) lb[i]=i;
    /**
    for(int i=1; i<=n; i++)
    {
        set<int>::iterator it=st[i].begin();
        cout<<i<<endl;
        while(it!=st[i].end()) {cout<<(*it)<<" "; it++;}
        cout<<endl;
    }*/
    long long sum=0;
    for(int i=1; i<=n; i++)
    {
        ///for(int k=0; k<brr; k++)
        ///{
        /**set<int>::iterator it=st[k].begin();
        cout<<k<<endl;
        while(it!=st[k].end()) {cout<<(*it)<<" "; it++;}
        cout<<endl;*/
        ///cout<<loc[k]<<" ";}
        ///cout<<endl;
        int t=rd[i].size();
        if(!t) continue;
        for(int j=0; j<t; j++)
        {
            int v=rd[i][j];
            while(v!=par[v]) v=par[v];
        }
        int tpr=rd[i][0];
        while(tpr!=par[tpr]) tpr=par[tpr];
        for(int j=0; j<t; j++)
        {
            int nr=rd[i][j];
            while(nr!=par[nr]) nr=par[nr];
            if(loc[nr] && lb[loc[nr]]!=lb[i])
            {
            int oprt=lb[i], nprt=lb[loc[nr]], prlab=oprt;
            if(st[oprt].size()>st[nprt].size())
            {
                set<int>::iterator it=st[nprt].begin();
                while(it!=st[nprt].end())
                {

                    st[oprt].insert(*it);
                    it++;
                }
            }
            else
            {
                prlab=lb[nprt];
                set<int>::iterator it=st[oprt].begin();
                while(it!=st[oprt].end())
                {
                    st[nprt].insert(*it);
                    it++;
                }
            }
            lb[i]=prlab;
            }
            if(nr==tpr) continue;
            if(db[tpr]>db[nr]) par[nr]=tpr;
            else if(db[tpr]<db[nr]) {par[tpr]=nr; tpr=nr;}
            else
            {
                par[nr]=tpr;
                db[tpr]++;
            }
        }
        loc[tpr]=i;
        st[lb[i]].insert(i);
        set<int>::iterator it=st[lb[i]].begin();
        while(it!=st[lb[i]].end())
        {
            if((*it)>=i) break;
            st[lb[i]].erase(it);
            it=st[lb[i]].begin();
        }
        sum+=st[lb[i]].size()-1;
        ///cout<<"otg: "<<i<<" "<<sum<<endl;
    }
    cout<<sum<<endl;
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 10 / 10