oj.uz

Submission #966380

# Submission time Handle Problem Language Result Execution time Memory
966380 2024-04-19T19:01:51 Z anango Roller Coaster Railroad (IOI16_railroad) C++17
100 / 100
 718 ms 105756 KB 
#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
class DSU {
private:
    int n;
    vector<int> parent;
    vector<int> rank;
public:
    DSU(int siz) {
        n=siz;
        parent=vector<int>(n,-1);
        rank=vector<int>(n,0);
        for (int i=0; i<n; i++) {
            parent[i]=i;
        }
    }
    int find(int node) {
        if (node==parent[node]) {
            return node;
        }
        return parent[node] = find(parent[node]);
    }
    void link(int u, int v) {
        u=find(u);
        v=find(v);
        if (u==v) {
            return;
        }
        if (rank[u]<rank[v]) {
            swap(u,v);
        }
        if (rank[u]==rank[v])  {
            rank[u]++;
        }
        parent[v]=u;
        return;
    }
    vector<int> getpar() {
        for (int i=0; i<n; i++) {
            find(i);
        }
        return parent;
    }
};


int plan_roller_coaster(vector<int32_t> s, vector<int32_t> t) {
    int n = (int) s.size();
    int INF=1000000007;
    set<int> crucial;
    for (int i=0; i<n; i++) {
        crucial.insert(s[i]);
        crucial.insert(t[i]);
    }
    crucial.insert(1);
    crucial.insert(INF);
    int cr = crucial.size();
    map<int,int> rev;
    vector<int> cval;
    for (auto i:crucial) {
        cval.push_back(i); //coordinate compression
    }
    // cout << "COMPRESSION" << endl;
    for (int i=0; i<cr; i++) {
        rev[cval[i]] = i;
        // cout << rev[cval[i]] <<" " << cval[i] << endl;
    }
    for (int i=0; i<n; i++) {
        s[i]=rev[s[i]];
        t[i]=rev[t[i]]; //sorry for polluting the arrays given, check this does not cause a bug in the orange juice
        
    }
    // cout << "OR ARRAYS" << endl;
    for (int i=0; i<n; i++) {
        // cout << s[i] <<" " << t[i] << endl;
    }
    vector<int> deltadiffarray(cr+1,0); //sum of blubberisation coefficients up to cr[i], each is cr[i] to cr[i+1] delta
    for (int i=0; i<n; i++) {
        deltadiffarray[s[i]]++;
        deltadiffarray[t[i]]--;
        // cout << "+"<<s[i] <<" -"<< t[i] << endl;
    }
    deltadiffarray[0]--;
    deltadiffarray[cr-1]++; //make the req val 1
    
    vector<int> deltas(cr,0);
    int su=0;
    int operations = 0;
    for (int i=0; i<cr-1; i++) {
        su+=deltadiffarray[i];
        deltas[i] = su;
        if (deltas[i]>0) {
            operations += deltas[i]*(cval[i+1] - cval[i]);
        }
    }
    // cout << "DELTA DIFFS" << endl;
    for (int i=0; i<cr; i++) {
        // cout << i <<" " << deltadiffarray[i] << endl;
    }
    // cout << "DELTAS" << endl;
    for (int i=0; i<cr; i++) {
        // cout << i <<" " << deltas[i] << endl;
    }
    DSU comp(cr);
    for (int i=0; i<n; i++) {
        comp.link(s[i],t[i]);
        // cout << "linking " << s[i] <<" " << t[i] << endl;
    }
    for (int i=0; i<cr-1; i++) {
        if (deltas[i]!=0) {
            comp.link(i,i+1);
        }
    }
    vector<int> components = comp.getpar();
    // cout << "COMPONENTS" << endl;
    for (int i=0; i<cr; i++) {
        // cout << i <<" " << components[i] << endl;
    }
    set<int> comps;
    for (auto i:components) {
        comps.insert(i);
    }
    vector<int> cvec;
    vector<int> revvec(400000, -1);
    for (auto i:comps) {
        cvec.push_back(i);
    }
    int tau = cvec.size();
    for (int i=0; i<tau; i++) {
        revvec[cvec[i]] = i;
    }
    vector<vector<pair<int,int>>> adjlist(tau);
    vector<vector<int>> edges;
    for (int i=0; i<cr-1; i++) {
        if (components[i] == components[i+1]) {
            continue;
        }
        int dist = cval[i+1] - cval[i];
        adjlist[revvec[components[i]]].push_back({revvec[components[i+1]],dist});
        adjlist[revvec[components[i+1]]].push_back({revvec[components[i]],dist});
        edges.push_back({revvec[components[i]],revvec[components[i+1]],dist});
    }
    //use the method of Kruskal, reusing the DSU, to find the component sum of min span tree
    DSU K(tau);
    sort(edges.begin(), edges.end(), [=](const vector<int> &v1, const vector<int> &v2) {
        return v1[2] < v2[2];
    });
    int cost=0;
    for (vector<int> edge:edges) {
        int u,v,w;
        u=edge[0];
        v=edge[1];
        w=edge[2];
        if (K.find(u)==K.find(v)) {
            continue;
        }
        K.link(u,v);
        cost+=w;
    }

    return operations+cost;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3420 KB n = 2
2 Correct 2 ms 3504 KB n = 2
3 Correct 1 ms 3420 KB n = 2
4 Correct 1 ms 3420 KB n = 2
5 Correct 1 ms 3512 KB n = 2
6 Correct 2 ms 3420 KB n = 2
7 Correct 1 ms 3420 KB n = 3
8 Correct 2 ms 3416 KB n = 3
9 Correct 1 ms 3420 KB n = 3
10 Correct 1 ms 3420 KB n = 8
11 Correct 1 ms 3416 KB n = 8
12 Correct 2 ms 3420 KB n = 8
13 Correct 2 ms 3420 KB n = 8
14 Correct 1 ms 3420 KB n = 8
15 Correct 1 ms 3420 KB n = 8
16 Correct 2 ms 3420 KB n = 8
17 Correct 1 ms 3416 KB n = 8
18 Correct 2 ms 3416 KB n = 8
19 Correct 2 ms 3420 KB n = 3
20 Correct 1 ms 3424 KB n = 7
21 Correct 2 ms 3420 KB n = 8
22 Correct 2 ms 3572 KB n = 8
23 Correct 1 ms 3508 KB n = 8
24 Correct 2 ms 3416 KB n = 8
25 Correct 1 ms 3420 KB n = 8

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3420 KB n = 2
2 Correct 2 ms 3504 KB n = 2
3 Correct 1 ms 3420 KB n = 2
4 Correct 1 ms 3420 KB n = 2
5 Correct 1 ms 3512 KB n = 2
6 Correct 2 ms 3420 KB n = 2
7 Correct 1 ms 3420 KB n = 3
8 Correct 2 ms 3416 KB n = 3
9 Correct 1 ms 3420 KB n = 3
10 Correct 1 ms 3420 KB n = 8
11 Correct 1 ms 3416 KB n = 8
12 Correct 2 ms 3420 KB n = 8
13 Correct 2 ms 3420 KB n = 8
14 Correct 1 ms 3420 KB n = 8
15 Correct 1 ms 3420 KB n = 8
16 Correct 2 ms 3420 KB n = 8
17 Correct 1 ms 3416 KB n = 8
18 Correct 2 ms 3416 KB n = 8
19 Correct 2 ms 3420 KB n = 3
20 Correct 1 ms 3424 KB n = 7
21 Correct 2 ms 3420 KB n = 8
22 Correct 2 ms 3572 KB n = 8
23 Correct 1 ms 3508 KB n = 8
24 Correct 2 ms 3416 KB n = 8
25 Correct 1 ms 3420 KB n = 8
26 Correct 1 ms 3416 KB n = 8
27 Correct 1 ms 3420 KB n = 8
28 Correct 2 ms 3420 KB n = 8
29 Correct 2 ms 3420 KB n = 16
30 Correct 1 ms 3424 KB n = 16
31 Correct 1 ms 3420 KB n = 16
32 Correct 2 ms 3416 KB n = 16
33 Correct 1 ms 3416 KB n = 16
34 Correct 1 ms 3420 KB n = 16
35 Correct 2 ms 3420 KB n = 16
36 Correct 1 ms 3420 KB n = 15
37 Correct 1 ms 3416 KB n = 8
38 Correct 1 ms 3412 KB n = 16
39 Correct 1 ms 3420 KB n = 16
40 Correct 1 ms 3420 KB n = 9
41 Correct 1 ms 3420 KB n = 16
42 Correct 2 ms 3420 KB n = 16
43 Correct 1 ms 3420 KB n = 16
44 Correct 1 ms 3508 KB n = 9
45 Correct 1 ms 3420 KB n = 15
46 Correct 1 ms 3420 KB n = 16
47 Correct 1 ms 3420 KB n = 16
48 Correct 2 ms 3676 KB n = 16

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 616 ms 72224 KB n = 199999
2 Correct 615 ms 71612 KB n = 199991
3 Correct 628 ms 71792 KB n = 199993
4 Correct 435 ms 56464 KB n = 152076
5 Correct 178 ms 35268 KB n = 93249
6 Correct 475 ms 60348 KB n = 199910
7 Correct 492 ms 69548 KB n = 199999
8 Correct 417 ms 60492 KB n = 199997
9 Correct 508 ms 62572 KB n = 171294
10 Correct 348 ms 51396 KB n = 140872
11 Correct 460 ms 60476 KB n = 199886
12 Correct 503 ms 71104 KB n = 199996
13 Correct 421 ms 63300 KB n = 200000
14 Correct 484 ms 77900 KB n = 199998
15 Correct 491 ms 76044 KB n = 200000
16 Correct 519 ms 78232 KB n = 199998
17 Correct 617 ms 71612 KB n = 200000
18 Correct 616 ms 68808 KB n = 190000
19 Correct 454 ms 64732 KB n = 177777
20 Correct 171 ms 37656 KB n = 100000
21 Correct 570 ms 72292 KB n = 200000
22 Correct 702 ms 104324 KB n = 200000
23 Correct 676 ms 71600 KB n = 200000

Subtask #4
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3420 KB n = 2
2 Correct 2 ms 3504 KB n = 2
3 Correct 1 ms 3420 KB n = 2
4 Correct 1 ms 3420 KB n = 2
5 Correct 1 ms 3512 KB n = 2
6 Correct 2 ms 3420 KB n = 2
7 Correct 1 ms 3420 KB n = 3
8 Correct 2 ms 3416 KB n = 3
9 Correct 1 ms 3420 KB n = 3
10 Correct 1 ms 3420 KB n = 8
11 Correct 1 ms 3416 KB n = 8
12 Correct 2 ms 3420 KB n = 8
13 Correct 2 ms 3420 KB n = 8
14 Correct 1 ms 3420 KB n = 8
15 Correct 1 ms 3420 KB n = 8
16 Correct 2 ms 3420 KB n = 8
17 Correct 1 ms 3416 KB n = 8
18 Correct 2 ms 3416 KB n = 8
19 Correct 2 ms 3420 KB n = 3
20 Correct 1 ms 3424 KB n = 7
21 Correct 2 ms 3420 KB n = 8
22 Correct 2 ms 3572 KB n = 8
23 Correct 1 ms 3508 KB n = 8
24 Correct 2 ms 3416 KB n = 8
25 Correct 1 ms 3420 KB n = 8
26 Correct 1 ms 3416 KB n = 8
27 Correct 1 ms 3420 KB n = 8
28 Correct 2 ms 3420 KB n = 8
29 Correct 2 ms 3420 KB n = 16
30 Correct 1 ms 3424 KB n = 16
31 Correct 1 ms 3420 KB n = 16
32 Correct 2 ms 3416 KB n = 16
33 Correct 1 ms 3416 KB n = 16
34 Correct 1 ms 3420 KB n = 16
35 Correct 2 ms 3420 KB n = 16
36 Correct 1 ms 3420 KB n = 15
37 Correct 1 ms 3416 KB n = 8
38 Correct 1 ms 3412 KB n = 16
39 Correct 1 ms 3420 KB n = 16
40 Correct 1 ms 3420 KB n = 9
41 Correct 1 ms 3420 KB n = 16
42 Correct 2 ms 3420 KB n = 16
43 Correct 1 ms 3420 KB n = 16
44 Correct 1 ms 3508 KB n = 9
45 Correct 1 ms 3420 KB n = 15
46 Correct 1 ms 3420 KB n = 16
47 Correct 1 ms 3420 KB n = 16
48 Correct 2 ms 3676 KB n = 16
49 Correct 616 ms 72224 KB n = 199999
50 Correct 615 ms 71612 KB n = 199991
51 Correct 628 ms 71792 KB n = 199993
52 Correct 435 ms 56464 KB n = 152076
53 Correct 178 ms 35268 KB n = 93249
54 Correct 475 ms 60348 KB n = 199910
55 Correct 492 ms 69548 KB n = 199999
56 Correct 417 ms 60492 KB n = 199997
57 Correct 508 ms 62572 KB n = 171294
58 Correct 348 ms 51396 KB n = 140872
59 Correct 460 ms 60476 KB n = 199886
60 Correct 503 ms 71104 KB n = 199996
61 Correct 421 ms 63300 KB n = 200000
62 Correct 484 ms 77900 KB n = 199998
63 Correct 491 ms 76044 KB n = 200000
64 Correct 519 ms 78232 KB n = 199998
65 Correct 617 ms 71612 KB n = 200000
66 Correct 616 ms 68808 KB n = 190000
67 Correct 454 ms 64732 KB n = 177777
68 Correct 171 ms 37656 KB n = 100000
69 Correct 570 ms 72292 KB n = 200000
70 Correct 702 ms 104324 KB n = 200000
71 Correct 676 ms 71600 KB n = 200000
72 Correct 596 ms 73148 KB n = 200000
73 Correct 637 ms 73092 KB n = 200000
74 Correct 641 ms 73132 KB n = 200000
75 Correct 577 ms 72964 KB n = 200000
76 Correct 718 ms 73116 KB n = 200000
77 Correct 269 ms 41788 KB n = 200000
78 Correct 421 ms 81480 KB n = 200000
79 Correct 580 ms 68700 KB n = 184307
80 Correct 147 ms 29828 KB n = 76040
81 Correct 491 ms 61884 KB n = 199981
82 Correct 489 ms 72496 KB n = 199994
83 Correct 504 ms 64768 KB n = 199996
84 Correct 489 ms 78552 KB n = 199998
85 Correct 556 ms 77864 KB n = 200000
86 Correct 550 ms 79616 KB n = 199998
87 Correct 552 ms 74072 KB n = 200000
88 Correct 585 ms 73912 KB n = 200000
89 Correct 564 ms 72988 KB n = 200000
90 Correct 549 ms 73880 KB n = 200000
91 Correct 710 ms 105756 KB n = 200000
92 Correct 587 ms 73660 KB n = 200000