oj.uz

Submission #813411

# Submission time Handle Problem Language Result Execution time Memory
813411 2023-08-07T17:26:21 Z mosiashvililuka Roller Coaster Railroad (IOI16_railroad) C++14
30 / 100
 743 ms 66792 KB 
#include<bits/stdc++.h>
#include "railroad.h"
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,S[200009],T[200009],pi,bo[400009],raod;
pair <int, int> p[400009];
map <int, int> m;
map <int, int>::iterator it;
vector <int> v[400009];
void dfs(int q){
    bo[q]=1;raod++;
    for(auto x:v[q]){
        if(bo[x]==1) continue;
        dfs(x);
    }
}
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) return 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]);
        }
    }

    for(i=1; i<=a; i++){
        v[m[S[i]]].push_back(m[T[i]]);
        v[m[T[i]]].push_back(m[S[i]]);
    }
    dfs(1);
    if(raod!=pi) return 1;
    return 0;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9696 KB n = 2
2 Correct 4 ms 9684 KB n = 2
3 Correct 4 ms 9684 KB n = 2
4 Correct 4 ms 9684 KB n = 2
5 Correct 4 ms 9684 KB n = 2
6 Incorrect 4 ms 9684 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 5 ms 9696 KB n = 2
2 Correct 4 ms 9684 KB n = 2
3 Correct 4 ms 9684 KB n = 2
4 Correct 4 ms 9684 KB n = 2
5 Correct 4 ms 9684 KB n = 2
6 Incorrect 4 ms 9684 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 743 ms 63420 KB n = 199999
2 Correct 211 ms 33632 KB n = 199991
3 Correct 200 ms 33680 KB n = 199993
4 Correct 633 ms 50560 KB n = 152076
5 Correct 283 ms 34924 KB n = 93249
6 Correct 632 ms 54992 KB n = 199910
7 Correct 631 ms 62284 KB n = 199999
8 Correct 590 ms 55200 KB n = 199997
9 Correct 598 ms 55724 KB n = 171294
10 Correct 470 ms 47708 KB n = 140872
11 Correct 618 ms 54700 KB n = 199886
12 Correct 619 ms 62540 KB n = 199996
13 Correct 561 ms 56892 KB n = 200000
14 Correct 149 ms 35848 KB n = 199998
15 Correct 152 ms 35456 KB n = 200000
16 Correct 173 ms 36608 KB n = 199998
17 Correct 173 ms 36932 KB n = 200000
18 Correct 173 ms 35656 KB n = 190000
19 Correct 495 ms 60360 KB n = 177777
20 Correct 271 ms 38128 KB n = 100000
21 Correct 631 ms 66588 KB n = 200000
22 Correct 549 ms 52716 KB n = 200000
23 Correct 735 ms 66792 KB n = 200000

Subtask #4
0 / 36.0

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