oj.uz

답안 #276937

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
276937 2020-08-20T19:59:02 Z MKopchev Roller Coaster Railroad (IOI16_railroad) C++14
100 / 100
 685 ms 43420 KB 
#include "railroad.h"
#include<bits/stdc++.h>
using namespace std;
const int nmax=2*2e5+42,inf=1e9;
int n;
vector<int> s,t;

int help[nmax],pointer=0;

int pref[nmax];

int parent[nmax];

int root(int node)
{
    if(parent[node]==node)return node;
    parent[node]=root(parent[node]);
    return parent[node];
}
void my_merge(int p,int q)
{
    p=root(p);
    q=root(q);
    parent[p]=q;
}

struct edge
{
    int u,v,cost;
};

vector<edge> given;

bool cmp(edge a,edge b)
{
    return a.cost<b.cost;
}

int on[nmax];
long long plan_roller_coaster(vector<int> S, vector<int> T)
{
    S.push_back(inf);
    T.push_back(1);

    n=S.size();

    s=S;
    t=T;

    long long outp=0;

    set<int> noted={1,inf};

    for(int i=0;i<n;i++)
    {
        noted.insert(s[i]);
        noted.insert(t[i]);
    }

    for(auto k:noted)
    {
        pointer++;
        help[pointer]=k;
    }

    for(int i=0;i<=pointer;i++)
    {
        parent[i]=i;
    }

    for(int i=0;i<n;i++)
    {
        int p=lower_bound(help+1,help+pointer+1,s[i])-help;
        int q=lower_bound(help+1,help+pointer+1,t[i])-help;

        my_merge(p,q);

        //cout<<p<<" "<<help[p]<<" "<<q<<" "<<help[q]<<endl;

        pref[p]++;
        pref[q]--;

        on[min(p,q)]++;
        on[max(p,q)]--;
    }

    for(int i=1;i<pointer;i++)
    {
        pref[i]+=pref[i-1];

        on[i]+=on[i-1];
        //cout<<i<<" -> "<<pref[i]<<" "<<help[i]<<" "<<help[i+1]<<endl;

        if(pref[i]>0)outp+=1LL*pref[i]*(help[i+1]-help[i]);

        if(pref[i])parent[root(i)]=root(i+1);


        edge cur;
        cur.u=i;
        cur.v=i+1;
        cur.cost=help[i+1]-help[i];

        given.push_back(cur);
    }

    sort(given.begin(),given.end(),cmp);

    for(auto k:given)
        if(root(k.u)!=root(k.v))
        {
            outp+=k.cost;
            parent[root(k.u)]=root(k.v);
        }

    return outp;
}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB n = 2
2 Correct 0 ms 384 KB n = 2
3 Correct 0 ms 384 KB n = 2
4 Correct 1 ms 384 KB n = 2
5 Correct 1 ms 384 KB n = 2
6 Correct 1 ms 384 KB n = 2
7 Correct 0 ms 384 KB n = 3
8 Correct 0 ms 384 KB n = 3
9 Correct 1 ms 384 KB n = 3
10 Correct 1 ms 384 KB n = 8
11 Correct 0 ms 384 KB n = 8
12 Correct 0 ms 384 KB n = 8
13 Correct 1 ms 384 KB n = 8
14 Correct 1 ms 384 KB n = 8
15 Correct 0 ms 384 KB n = 8
16 Correct 1 ms 384 KB n = 8
17 Correct 0 ms 384 KB n = 8
18 Correct 0 ms 384 KB n = 8
19 Correct 1 ms 384 KB n = 3
20 Correct 0 ms 384 KB n = 7
21 Correct 1 ms 384 KB n = 8
22 Correct 1 ms 384 KB n = 8
23 Correct 1 ms 384 KB n = 8
24 Correct 1 ms 384 KB n = 8
25 Correct 1 ms 384 KB n = 8

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB n = 2
2 Correct 0 ms 384 KB n = 2
3 Correct 0 ms 384 KB n = 2
4 Correct 1 ms 384 KB n = 2
5 Correct 1 ms 384 KB n = 2
6 Correct 1 ms 384 KB n = 2
7 Correct 0 ms 384 KB n = 3
8 Correct 0 ms 384 KB n = 3
9 Correct 1 ms 384 KB n = 3
10 Correct 1 ms 384 KB n = 8
11 Correct 0 ms 384 KB n = 8
12 Correct 0 ms 384 KB n = 8
13 Correct 1 ms 384 KB n = 8
14 Correct 1 ms 384 KB n = 8
15 Correct 0 ms 384 KB n = 8
16 Correct 1 ms 384 KB n = 8
17 Correct 0 ms 384 KB n = 8
18 Correct 0 ms 384 KB n = 8
19 Correct 1 ms 384 KB n = 3
20 Correct 0 ms 384 KB n = 7
21 Correct 1 ms 384 KB n = 8
22 Correct 1 ms 384 KB n = 8
23 Correct 1 ms 384 KB n = 8
24 Correct 1 ms 384 KB n = 8
25 Correct 1 ms 384 KB n = 8
26 Correct 1 ms 384 KB n = 8
27 Correct 1 ms 384 KB n = 8
28 Correct 1 ms 384 KB n = 8
29 Correct 0 ms 384 KB n = 16
30 Correct 0 ms 384 KB n = 16
31 Correct 1 ms 384 KB n = 16
32 Correct 0 ms 384 KB n = 16
33 Correct 0 ms 384 KB n = 16
34 Correct 0 ms 384 KB n = 16
35 Correct 1 ms 384 KB n = 16
36 Correct 1 ms 384 KB n = 15
37 Correct 1 ms 384 KB n = 8
38 Correct 1 ms 384 KB n = 16
39 Correct 1 ms 384 KB n = 16
40 Correct 1 ms 384 KB n = 9
41 Correct 1 ms 384 KB n = 16
42 Correct 0 ms 384 KB n = 16
43 Correct 1 ms 384 KB n = 16
44 Correct 0 ms 384 KB n = 9
45 Correct 1 ms 384 KB n = 15
46 Correct 1 ms 384 KB n = 16
47 Correct 1 ms 384 KB n = 16
48 Correct 0 ms 384 KB n = 16

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 636 ms 36528 KB n = 199999
2 Correct 685 ms 36440 KB n = 199991
3 Correct 676 ms 36384 KB n = 199993
4 Correct 470 ms 30016 KB n = 152076
5 Correct 288 ms 17832 KB n = 93249
6 Correct 509 ms 31956 KB n = 199910
7 Correct 475 ms 36052 KB n = 199999
8 Correct 462 ms 32084 KB n = 199997
9 Correct 501 ms 32944 KB n = 171294
10 Correct 414 ms 28320 KB n = 140872
11 Correct 504 ms 32212 KB n = 199886
12 Correct 514 ms 39348 KB n = 199996
13 Correct 441 ms 35796 KB n = 200000
14 Correct 469 ms 39248 KB n = 199998
15 Correct 476 ms 38740 KB n = 200000
16 Correct 480 ms 39636 KB n = 199998
17 Correct 535 ms 43348 KB n = 200000
18 Correct 548 ms 39516 KB n = 190000
19 Correct 465 ms 39936 KB n = 177777
20 Correct 237 ms 20324 KB n = 100000
21 Correct 583 ms 40280 KB n = 200000
22 Correct 564 ms 40200 KB n = 200000
23 Correct 588 ms 40404 KB n = 200000

Subtask #4
36.0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB n = 2
2 Correct 0 ms 384 KB n = 2
3 Correct 0 ms 384 KB n = 2
4 Correct 1 ms 384 KB n = 2
5 Correct 1 ms 384 KB n = 2
6 Correct 1 ms 384 KB n = 2
7 Correct 0 ms 384 KB n = 3
8 Correct 0 ms 384 KB n = 3
9 Correct 1 ms 384 KB n = 3
10 Correct 1 ms 384 KB n = 8
11 Correct 0 ms 384 KB n = 8
12 Correct 0 ms 384 KB n = 8
13 Correct 1 ms 384 KB n = 8
14 Correct 1 ms 384 KB n = 8
15 Correct 0 ms 384 KB n = 8
16 Correct 1 ms 384 KB n = 8
17 Correct 0 ms 384 KB n = 8
18 Correct 0 ms 384 KB n = 8
19 Correct 1 ms 384 KB n = 3
20 Correct 0 ms 384 KB n = 7
21 Correct 1 ms 384 KB n = 8
22 Correct 1 ms 384 KB n = 8
23 Correct 1 ms 384 KB n = 8
24 Correct 1 ms 384 KB n = 8
25 Correct 1 ms 384 KB n = 8
26 Correct 1 ms 384 KB n = 8
27 Correct 1 ms 384 KB n = 8
28 Correct 1 ms 384 KB n = 8
29 Correct 0 ms 384 KB n = 16
30 Correct 0 ms 384 KB n = 16
31 Correct 1 ms 384 KB n = 16
32 Correct 0 ms 384 KB n = 16
33 Correct 0 ms 384 KB n = 16
34 Correct 0 ms 384 KB n = 16
35 Correct 1 ms 384 KB n = 16
36 Correct 1 ms 384 KB n = 15
37 Correct 1 ms 384 KB n = 8
38 Correct 1 ms 384 KB n = 16
39 Correct 1 ms 384 KB n = 16
40 Correct 1 ms 384 KB n = 9
41 Correct 1 ms 384 KB n = 16
42 Correct 0 ms 384 KB n = 16
43 Correct 1 ms 384 KB n = 16
44 Correct 0 ms 384 KB n = 9
45 Correct 1 ms 384 KB n = 15
46 Correct 1 ms 384 KB n = 16
47 Correct 1 ms 384 KB n = 16
48 Correct 0 ms 384 KB n = 16
49 Correct 636 ms 36528 KB n = 199999
50 Correct 685 ms 36440 KB n = 199991
51 Correct 676 ms 36384 KB n = 199993
52 Correct 470 ms 30016 KB n = 152076
53 Correct 288 ms 17832 KB n = 93249
54 Correct 509 ms 31956 KB n = 199910
55 Correct 475 ms 36052 KB n = 199999
56 Correct 462 ms 32084 KB n = 199997
57 Correct 501 ms 32944 KB n = 171294
58 Correct 414 ms 28320 KB n = 140872
59 Correct 504 ms 32212 KB n = 199886
60 Correct 514 ms 39348 KB n = 199996
61 Correct 441 ms 35796 KB n = 200000
62 Correct 469 ms 39248 KB n = 199998
63 Correct 476 ms 38740 KB n = 200000
64 Correct 480 ms 39636 KB n = 199998
65 Correct 535 ms 43348 KB n = 200000
66 Correct 548 ms 39516 KB n = 190000
67 Correct 465 ms 39936 KB n = 177777
68 Correct 237 ms 20324 KB n = 100000
69 Correct 583 ms 40280 KB n = 200000
70 Correct 564 ms 40200 KB n = 200000
71 Correct 588 ms 40404 KB n = 200000
72 Correct 620 ms 40340 KB n = 200000
73 Correct 612 ms 40272 KB n = 200000
74 Correct 604 ms 40300 KB n = 200000
75 Correct 512 ms 40284 KB n = 200000
76 Correct 503 ms 40276 KB n = 200000
77 Correct 339 ms 27092 KB n = 200000
78 Correct 319 ms 24664 KB n = 200000
79 Correct 608 ms 38068 KB n = 184307
80 Correct 187 ms 16664 KB n = 76040
81 Correct 493 ms 34900 KB n = 199981
82 Correct 506 ms 39276 KB n = 199994
83 Correct 447 ms 35924 KB n = 199996
84 Correct 443 ms 39176 KB n = 199998
85 Correct 449 ms 38472 KB n = 200000
86 Correct 479 ms 39636 KB n = 199998
87 Correct 516 ms 43420 KB n = 200000
88 Correct 539 ms 40920 KB n = 200000
89 Correct 528 ms 43348 KB n = 200000
90 Correct 562 ms 40272 KB n = 200000
91 Correct 543 ms 40200 KB n = 200000
92 Correct 618 ms 40276 KB n = 200000