oj.uz

Submission #821265

# Submission time Handle Problem Language Result Execution time Memory
821265 2023-08-11T08:34:26 Z vnm06 Marshmallow Molecules (CCO19_day2problem2) C++14
10 / 25
 4000 ms 24032 KB 
#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])
            {
            int oprt=lb[i], nprt=lb[loc[nr]], prlab=oprt;
            ///cout<<"gewb: "<<tpr<<" "<<nr<<" "<<oprt<<" "<<nprt<<endl;
            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[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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9728 KB Output is correct
3 Correct 12 ms 10024 KB Output is correct
4 Correct 7 ms 9840 KB Output is correct
5 Correct 7 ms 9812 KB Output is correct
6 Correct 7 ms 9812 KB Output is correct
7 Correct 7 ms 9812 KB Output is correct
8 Correct 7 ms 9812 KB Output is correct
9 Correct 5 ms 9684 KB Output is correct
10 Correct 6 ms 9812 KB Output is correct
11 Correct 6 ms 9776 KB Output is correct
12 Correct 9 ms 9868 KB Output is correct
13 Correct 7 ms 9812 KB Output is correct
14 Correct 7 ms 9812 KB Output is correct
15 Correct 5 ms 9684 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9728 KB Output is correct
3 Correct 12 ms 10024 KB Output is correct
4 Correct 7 ms 9840 KB Output is correct
5 Correct 7 ms 9812 KB Output is correct
6 Correct 7 ms 9812 KB Output is correct
7 Correct 7 ms 9812 KB Output is correct
8 Correct 7 ms 9812 KB Output is correct
9 Correct 5 ms 9684 KB Output is correct
10 Correct 6 ms 9812 KB Output is correct
11 Correct 6 ms 9776 KB Output is correct
12 Correct 9 ms 9868 KB Output is correct
13 Correct 7 ms 9812 KB Output is correct
14 Correct 7 ms 9812 KB Output is correct
15 Correct 5 ms 9684 KB Output is correct
16 Execution timed out 4048 ms 16552 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 23424 KB Output is correct
2 Correct 133 ms 23892 KB Output is correct
3 Correct 100 ms 23908 KB Output is correct
4 Correct 102 ms 23508 KB Output is correct
5 Correct 102 ms 23884 KB Output is correct
6 Correct 108 ms 23960 KB Output is correct
7 Correct 96 ms 23468 KB Output is correct
8 Correct 118 ms 23768 KB Output is correct
9 Correct 103 ms 23884 KB Output is correct
10 Correct 110 ms 23520 KB Output is correct
11 Correct 107 ms 24032 KB Output is correct
12 Correct 112 ms 23980 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9728 KB Output is correct
3 Correct 12 ms 10024 KB Output is correct
4 Correct 7 ms 9840 KB Output is correct
5 Correct 7 ms 9812 KB Output is correct
6 Correct 7 ms 9812 KB Output is correct
7 Correct 7 ms 9812 KB Output is correct
8 Correct 7 ms 9812 KB Output is correct
9 Correct 5 ms 9684 KB Output is correct
10 Correct 6 ms 9812 KB Output is correct
11 Correct 6 ms 9776 KB Output is correct
12 Correct 9 ms 9868 KB Output is correct
13 Correct 7 ms 9812 KB Output is correct
14 Correct 7 ms 9812 KB Output is correct
15 Correct 5 ms 9684 KB Output is correct
16 Execution timed out 4048 ms 16552 KB Time limit exceeded
17 Halted 0 ms 0 KB -