oj.uz

Submission #821268

# Submission time Handle Problem Language Result Execution time Memory
821268 2023-08-11T08:35:26 Z vnm06 Marshmallow Molecules (CCO19_day2problem2) C++14
10 / 25
 4000 ms 24036 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(!st[lb[i]].empty() && 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 4 ms 9684 KB Output is correct
2 Correct 4 ms 9684 KB Output is correct
3 Correct 9 ms 9980 KB Output is correct
4 Correct 6 ms 9868 KB Output is correct
5 Correct 6 ms 9812 KB Output is correct
6 Correct 7 ms 9812 KB Output is correct
7 Correct 6 ms 9812 KB Output is correct
8 Correct 6 ms 9812 KB Output is correct
9 Correct 4 ms 9684 KB Output is correct
10 Correct 6 ms 9812 KB Output is correct
11 Correct 6 ms 9812 KB Output is correct
12 Correct 7 ms 9812 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 4 ms 9684 KB Output is correct
2 Correct 4 ms 9684 KB Output is correct
3 Correct 9 ms 9980 KB Output is correct
4 Correct 6 ms 9868 KB Output is correct
5 Correct 6 ms 9812 KB Output is correct
6 Correct 7 ms 9812 KB Output is correct
7 Correct 6 ms 9812 KB Output is correct
8 Correct 6 ms 9812 KB Output is correct
9 Correct 4 ms 9684 KB Output is correct
10 Correct 6 ms 9812 KB Output is correct
11 Correct 6 ms 9812 KB Output is correct
12 Correct 7 ms 9812 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 Correct 3910 ms 16568 KB Output is correct
17 Execution timed out 4059 ms 16428 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 23472 KB Output is correct
2 Correct 98 ms 23784 KB Output is correct
3 Correct 96 ms 23884 KB Output is correct
4 Correct 97 ms 23420 KB Output is correct
5 Correct 104 ms 23824 KB Output is correct
6 Correct 105 ms 24036 KB Output is correct
7 Correct 107 ms 23512 KB Output is correct
8 Correct 107 ms 23752 KB Output is correct
9 Correct 100 ms 23916 KB Output is correct
10 Correct 103 ms 23436 KB Output is correct
11 Correct 113 ms 23908 KB Output is correct
12 Correct 97 ms 23904 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 4 ms 9684 KB Output is correct
3 Correct 9 ms 9980 KB Output is correct
4 Correct 6 ms 9868 KB Output is correct
5 Correct 6 ms 9812 KB Output is correct
6 Correct 7 ms 9812 KB Output is correct
7 Correct 6 ms 9812 KB Output is correct
8 Correct 6 ms 9812 KB Output is correct
9 Correct 4 ms 9684 KB Output is correct
10 Correct 6 ms 9812 KB Output is correct
11 Correct 6 ms 9812 KB Output is correct
12 Correct 7 ms 9812 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 Correct 3910 ms 16568 KB Output is correct
17 Execution timed out 4059 ms 16428 KB Time limit exceeded
18 Halted 0 ms 0 KB -