oj.uz

답안 #821290

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
821290 2023-08-11T08:43:58 Z vnm06 Marshmallow Molecules (CCO19_day2problem2) C++14
10 / 25
 4000 ms 22884 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;
            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.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 6 ms 9708 KB Output is correct
3 Correct 9 ms 9980 KB Output is correct
4 Correct 7 ms 9812 KB Output is correct
5 Correct 6 ms 9772 KB Output is correct
6 Correct 7 ms 9856 KB Output is correct
7 Correct 8 ms 9812 KB Output is correct
8 Correct 7 ms 9860 KB Output is correct
9 Correct 4 ms 9684 KB Output is correct
10 Correct 6 ms 9848 KB Output is correct
11 Correct 6 ms 9812 KB Output is correct
12 Correct 7 ms 9940 KB Output is correct
13 Correct 7 ms 9812 KB Output is correct
14 Correct 9 ms 9940 KB Output is correct
15 Correct 5 ms 9716 KB Output is correct

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 6 ms 9708 KB Output is correct
3 Correct 9 ms 9980 KB Output is correct
4 Correct 7 ms 9812 KB Output is correct
5 Correct 6 ms 9772 KB Output is correct
6 Correct 7 ms 9856 KB Output is correct
7 Correct 8 ms 9812 KB Output is correct
8 Correct 7 ms 9860 KB Output is correct
9 Correct 4 ms 9684 KB Output is correct
10 Correct 6 ms 9848 KB Output is correct
11 Correct 6 ms 9812 KB Output is correct
12 Correct 7 ms 9940 KB Output is correct
13 Correct 7 ms 9812 KB Output is correct
14 Correct 9 ms 9940 KB Output is correct
15 Correct 5 ms 9716 KB Output is correct
16 Correct 3742 ms 16936 KB Output is correct
17 Execution timed out 4065 ms 16784 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #3
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 96 ms 22884 KB Output is correct
2 Correct 102 ms 21224 KB Output is correct
3 Correct 94 ms 20464 KB Output is correct
4 Correct 101 ms 22576 KB Output is correct
5 Correct 106 ms 21324 KB Output is correct
6 Correct 105 ms 20588 KB Output is correct
7 Correct 99 ms 22496 KB Output is correct
8 Correct 97 ms 21228 KB Output is correct
9 Correct 92 ms 20460 KB Output is correct
10 Correct 120 ms 22584 KB Output is correct
11 Correct 104 ms 21268 KB Output is correct
12 Correct 97 ms 20452 KB Output is correct

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 6 ms 9708 KB Output is correct
3 Correct 9 ms 9980 KB Output is correct
4 Correct 7 ms 9812 KB Output is correct
5 Correct 6 ms 9772 KB Output is correct
6 Correct 7 ms 9856 KB Output is correct
7 Correct 8 ms 9812 KB Output is correct
8 Correct 7 ms 9860 KB Output is correct
9 Correct 4 ms 9684 KB Output is correct
10 Correct 6 ms 9848 KB Output is correct
11 Correct 6 ms 9812 KB Output is correct
12 Correct 7 ms 9940 KB Output is correct
13 Correct 7 ms 9812 KB Output is correct
14 Correct 9 ms 9940 KB Output is correct
15 Correct 5 ms 9716 KB Output is correct
16 Correct 3742 ms 16936 KB Output is correct
17 Execution timed out 4065 ms 16784 KB Time limit exceeded
18 Halted 0 ms 0 KB -