oj.uz

Submission #813439

# Submission time Handle Problem Language Result Execution time Memory
813439 2023-08-07T17:57:43 Z mosiashvililuka Roller Coaster Railroad (IOI16_railroad) C++14
30 / 100
 643 ms 42276 KB 
#include<bits/stdc++.h>
#include "railroad.h"
using namespace std;
long long pas;
int a,b,c,d,e,i,j,ii,jj,zx,xc,S[200009],T[200009],pi,msh[400009],zm[400009],cmp;
pair <int, int> p[400009];
map <int, int> m;
map <int, int>::iterator it;
//vector <int> v[400009];
vector <pair <pair <int, int>, int> > edges;
int fnd(int q){
    if(msh[q]==q) return q; else return msh[q]=fnd(msh[q]);
}
void mrg(int q, int w){
    q=fnd(q);w=fnd(w);
    if(q==w) return;
    cmp--;
    if(zm[q]<zm[w]) swap(q,w);
    if(zm[q]==zm[w]) zm[q]++;
    msh[w]=q;
}
long long plan_roller_coaster(std::vector<int> Ss, std::vector<int> Tt) {
    a=Ss.size();
    for(i=1; i<=a; i++){
        S[i]=Ss[i-1];T[i]=Tt[i-1];
    }

    for(i=1; i<=a; i++){
        m[S[i]]++;m[T[i]]--;
    }
    zx=0;xc=0;
    pi++;p[pi]={0,0};
    xc++;m[0]=xc;
    for(it=m.begin(); it!=m.end(); it++){
        if((*it).first==0) continue;
        zx+=(*it).second;
        pi++;p[pi]={(*it).first,zx};
        xc++;
        (*it).second=xc;
        if(zx>1){
            edges.push_back({{m[p[pi-1].first],m[p[pi].first]},0});
            pas+=zx-1;
        }
    }
    pi++;p[pi]={1000000003,zx};
    xc++;m[p[pi].first]=xc;

    for(ii=1; ii<pi; ii++){
        if(p[ii].second<1){
            /*v[m[p[ii].first]].push_back(m[p[ii+1].first]);
            v[m[p[ii+1].first]].push_back(m[p[ii].first]);*/
            edges.push_back({{m[p[ii].first],m[p[ii+1].first]},0});
        }
    }

    for(i=1; i<=a; i++){
        /*v[m[S[i]]].push_back(m[T[i]]);
        v[m[T[i]]].push_back(m[S[i]]);*/
        edges.push_back({{m[S[i]],m[T[i]]},0});
    }
    /*dfs(1);
    if(raod!=pi) return 1;*/
    for(ii=1; ii<pi; ii++){
        edges.push_back({{m[p[ii].first],m[p[ii+1].first]},p[ii+1].first-p[ii].first});
    }
    for(auto &x:edges){
        swap(x.first.first,x.second);
    }
    sort(edges.begin(),edges.end());
    for(auto &x:edges){
        swap(x.first.first,x.second);
    }
    for(i=1; i<=pi; i++){
        msh[i]=i;zm[i]=0;
    }
    cmp=pi;
    //cout<<pas<<"\n";
    for(auto x:edges){
        if(cmp==1) break;
        //cout<<x.first.first<<" "<<x.first.second<<" "<<x.second<<"    :";
        if(fnd(x.first.first)==fnd(x.first.second)) continue;
        mrg(x.first.first,x.first.second);
        //cout<<cmp<<"\n";
        pas+=x.second;
    }
    return pas;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 2
2 Correct 0 ms 340 KB n = 2
3 Correct 0 ms 212 KB n = 2
4 Correct 0 ms 212 KB n = 2
5 Correct 0 ms 340 KB n = 2
6 Incorrect 1 ms 308 KB answer is not correct: 1 instead of 523688153
7 Halted 0 ms 0 KB -

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 2
2 Correct 0 ms 340 KB n = 2
3 Correct 0 ms 212 KB n = 2
4 Correct 0 ms 212 KB n = 2
5 Correct 0 ms 340 KB n = 2
6 Incorrect 1 ms 308 KB answer is not correct: 1 instead of 523688153
7 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 643 ms 42188 KB n = 199999
2 Correct 580 ms 42176 KB n = 199991
3 Correct 591 ms 42276 KB n = 199993
4 Correct 416 ms 33204 KB n = 152076
5 Correct 256 ms 20008 KB n = 93249
6 Correct 523 ms 35844 KB n = 199910
7 Correct 514 ms 41376 KB n = 199999
8 Correct 466 ms 36144 KB n = 199997
9 Correct 507 ms 36236 KB n = 171294
10 Correct 405 ms 31828 KB n = 140872
11 Correct 486 ms 36356 KB n = 199886
12 Correct 569 ms 41424 KB n = 199996
13 Correct 496 ms 37324 KB n = 200000
14 Correct 523 ms 39816 KB n = 199998
15 Correct 539 ms 39180 KB n = 200000
16 Correct 527 ms 40264 KB n = 199998
17 Correct 525 ms 42132 KB n = 200000
18 Correct 526 ms 40044 KB n = 190000
19 Correct 538 ms 37492 KB n = 177777
20 Correct 213 ms 21408 KB n = 100000
21 Correct 575 ms 42144 KB n = 200000
22 Correct 533 ms 39780 KB n = 200000
23 Correct 602 ms 39836 KB n = 200000

Subtask #4
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 2
2 Correct 0 ms 340 KB n = 2
3 Correct 0 ms 212 KB n = 2
4 Correct 0 ms 212 KB n = 2
5 Correct 0 ms 340 KB n = 2
6 Incorrect 1 ms 308 KB answer is not correct: 1 instead of 523688153
7 Halted 0 ms 0 KB -