oj.uz

답안 #270649

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
270649 2020-08-17T20:38:10 Z stoyan_malinin Roller Coaster Railroad (IOI16_railroad) C++14
100 / 100
 1054 ms 48220 KB 
#include "railroad.h"
//#include "grader.cpp"

#include <set>
#include <map>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const long long inf = 1e18 + 5;

struct DSU
{
    vector <int> parent;

    DSU(){}
    DSU(int n)
    {
        this->parent.resize(n+5);
        for(int i = 0;i<=n;i++) this->parent[i] = i;
    }

    int Find(int x)
    {
        if(parent[x]==x) return x;

        parent[x] = Find(parent[x]);
        return parent[x];
    }

    bool Union(int u, int v)
    {
        u = Find(u);
        v = Find(v);
        if(u==v) return false;

        parent[v] = u;
        return true;
    }
};

int n;
vector <int> s, t;

map <int, int> numCode;
vector <int> invCode;

void init()
{
    set <int> nums;
    for(int x: s) nums.insert(x);
    for(int x: t) nums.insert(x);

    int ind = 0;
    invCode.resize(nums.size()+5);

    for(int x: nums)
    {
        numCode[x] = ind;
        invCode[ind] = x;

        ind++;
        //cout << x << " -> " << code[x] << '\n';
    }

    for(int &x: s) x = numCode[x];
    for(int &x: t) x = numCode[x];
}

long long plan_roller_coaster(vector<int> _s, vector<int> _t)
{
    _s.push_back(int(1e9+5));
    _t.push_back(1);

    s = _s;
    t = _t;
    n = s.size();
    init();

    DSU T = DSU(2*n+5);
    long long answer = 0;

    vector <int> start, finish;
    finish.assign(numCode.size()+5, 0);
    start.assign(numCode.size()+5, 0);

    //cout << '\n';

    for(int i = 0;i<n;i++)
    {
        //cout << s[i] << " " << t[i] << '\n';
        T.Union(s[i], t[i]);

        int x = s[i];
        int y = t[i];
        if(x>y) swap(x, y);

        start[x] += ((s[i]<t[i])?+1:-1);
        finish[y] += ((s[i]<t[i])?+1:-1);
    }

    int val = 0;
    for(int i = 0;i<numCode.size()-1;i++)
    {
        val += start[i];
        val -= finish[i];

        //cout << i << " => " << val << " || " << start[i] << " " << finish[i] << '\n';
        if(val>0)
        {
            T.Union(i, i+1);
            answer += val*1LL*(invCode[i+1]-invCode[i]);
        }
        else if(val<0)
        {
            T.Union(i, i+1);
        }
    }

    vector <pair <long long, int>> edges;
    for(int i = 0;i<numCode.size()-1;i++)
    {
        if(T.Find(i)!=T.Find(i+1))
        {
            //cout << " -> " << i << '\n';
            edges.push_back({invCode[i+1]-invCode[i], i});
        }
    }

    sort(edges.begin(), edges.end());
    for(pair <long long, int> x: edges)
    {
        if(T.Union(x.second, x.second+1)==true) answer += x.first;
    }

    return answer;
}
/*
2
4 2
3 5

4
1 7
4 3
5 8
6 6
*/

Compilation message

railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:105:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |     for(int i = 0;i<numCode.size()-1;i++)
      |                   ~^~~~~~~~~~~~~~~~~
railroad.cpp:123:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |     for(int i = 0;i<numCode.size()-1;i++)
      |                   ~^~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

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

Subtask #2
23.0 / 23.0

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

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 819 ms 44120 KB n = 199999
2 Correct 852 ms 44248 KB n = 199991
3 Correct 812 ms 48088 KB n = 199993
4 Correct 564 ms 36176 KB n = 152076
5 Correct 313 ms 22552 KB n = 93249
6 Correct 783 ms 39768 KB n = 199910
7 Correct 886 ms 46552 KB n = 199999
8 Correct 791 ms 40152 KB n = 199997
9 Correct 673 ms 41144 KB n = 171294
10 Correct 488 ms 33964 KB n = 140872
11 Correct 759 ms 40512 KB n = 199886
12 Correct 855 ms 47016 KB n = 199996
13 Correct 738 ms 41840 KB n = 200000
14 Correct 814 ms 47320 KB n = 199998
15 Correct 800 ms 46680 KB n = 200000
16 Correct 910 ms 48188 KB n = 199998
17 Correct 725 ms 48088 KB n = 200000
18 Correct 839 ms 45736 KB n = 190000
19 Correct 560 ms 42760 KB n = 177777
20 Correct 313 ms 24168 KB n = 100000
21 Correct 818 ms 48192 KB n = 200000
22 Correct 848 ms 48220 KB n = 200000
23 Correct 997 ms 48216 KB n = 200000

Subtask #4
36.0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 KB n = 2
2 Correct 0 ms 256 KB n = 2
3 Correct 0 ms 256 KB n = 2
4 Correct 1 ms 256 KB n = 2
5 Correct 1 ms 256 KB n = 2
6 Correct 0 ms 256 KB n = 2
7 Correct 1 ms 384 KB n = 3
8 Correct 0 ms 256 KB n = 3
9 Correct 1 ms 256 KB n = 3
10 Correct 0 ms 256 KB n = 8
11 Correct 0 ms 384 KB n = 8
12 Correct 1 ms 256 KB n = 8
13 Correct 1 ms 384 KB n = 8
14 Correct 1 ms 256 KB n = 8
15 Correct 4 ms 384 KB n = 8
16 Correct 0 ms 256 KB n = 8
17 Correct 0 ms 256 KB n = 8
18 Correct 1 ms 256 KB n = 8
19 Correct 1 ms 256 KB n = 3
20 Correct 1 ms 256 KB n = 7
21 Correct 1 ms 384 KB n = 8
22 Correct 0 ms 256 KB n = 8
23 Correct 1 ms 256 KB n = 8
24 Correct 0 ms 256 KB n = 8
25 Correct 0 ms 256 KB n = 8
26 Correct 0 ms 256 KB n = 8
27 Correct 1 ms 256 KB n = 8
28 Correct 0 ms 256 KB n = 8
29 Correct 1 ms 256 KB n = 16
30 Correct 0 ms 256 KB n = 16
31 Correct 0 ms 384 KB n = 16
32 Correct 1 ms 256 KB n = 16
33 Correct 0 ms 256 KB n = 16
34 Correct 1 ms 256 KB n = 16
35 Correct 1 ms 256 KB n = 16
36 Correct 0 ms 256 KB n = 15
37 Correct 1 ms 256 KB n = 8
38 Correct 0 ms 256 KB n = 16
39 Correct 0 ms 256 KB n = 16
40 Correct 1 ms 256 KB n = 9
41 Correct 0 ms 256 KB n = 16
42 Correct 0 ms 256 KB n = 16
43 Correct 1 ms 384 KB n = 16
44 Correct 0 ms 384 KB n = 9
45 Correct 1 ms 256 KB n = 15
46 Correct 0 ms 256 KB n = 16
47 Correct 1 ms 384 KB n = 16
48 Correct 1 ms 256 KB n = 16
49 Correct 819 ms 44120 KB n = 199999
50 Correct 852 ms 44248 KB n = 199991
51 Correct 812 ms 48088 KB n = 199993
52 Correct 564 ms 36176 KB n = 152076
53 Correct 313 ms 22552 KB n = 93249
54 Correct 783 ms 39768 KB n = 199910
55 Correct 886 ms 46552 KB n = 199999
56 Correct 791 ms 40152 KB n = 199997
57 Correct 673 ms 41144 KB n = 171294
58 Correct 488 ms 33964 KB n = 140872
59 Correct 759 ms 40512 KB n = 199886
60 Correct 855 ms 47016 KB n = 199996
61 Correct 738 ms 41840 KB n = 200000
62 Correct 814 ms 47320 KB n = 199998
63 Correct 800 ms 46680 KB n = 200000
64 Correct 910 ms 48188 KB n = 199998
65 Correct 725 ms 48088 KB n = 200000
66 Correct 839 ms 45736 KB n = 190000
67 Correct 560 ms 42760 KB n = 177777
68 Correct 313 ms 24168 KB n = 100000
69 Correct 818 ms 48192 KB n = 200000
70 Correct 848 ms 48220 KB n = 200000
71 Correct 997 ms 48216 KB n = 200000
72 Correct 1054 ms 48088 KB n = 200000
73 Correct 919 ms 48068 KB n = 200000
74 Correct 924 ms 48088 KB n = 200000
75 Correct 774 ms 47988 KB n = 200000
76 Correct 759 ms 48088 KB n = 200000
77 Correct 634 ms 28504 KB n = 200000
78 Correct 609 ms 31668 KB n = 200000
79 Correct 829 ms 44088 KB n = 184307
80 Correct 240 ms 18564 KB n = 76040
81 Correct 865 ms 40328 KB n = 199981
82 Correct 859 ms 46952 KB n = 199994
83 Correct 842 ms 41848 KB n = 199996
84 Correct 841 ms 47248 KB n = 199998
85 Correct 855 ms 46584 KB n = 200000
86 Correct 888 ms 48216 KB n = 199998
87 Correct 696 ms 48096 KB n = 200000
88 Correct 881 ms 47984 KB n = 200000
89 Correct 731 ms 48092 KB n = 200000
90 Correct 943 ms 48012 KB n = 200000
91 Correct 954 ms 48128 KB n = 200000
92 Correct 889 ms 48088 KB n = 200000