Submission #948927

#	Time	Username	Problem	Language	Result	Execution time	Memory
948927		mariaclara	Roller Coaster Railroad (IOI16_railroad)	C++17	100 / 100	602 ms	58864 KiB

railroad

#include "railroad.h"
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 4e5+5;
#define all(x) x.begin(), x.end()
#define mk make_pair
#define pb push_back
#define fr first
#define sc second

int pai[MAXN], sz[MAXN];

int find(int x) {
    if(x == pai[x]) return x;
    return pai[x] = find(pai[x]);
}

void join(int x, int y) {
    x = find(x);
    y = find(y);

    if(x == y) return;
    if(sz[x] <= sz[y]) {
        pai[x] = y;
        sz[y] += sz[x];
    }
    else {
        pai[y] = x;
        sz[x] += sz[y];
    }
}

ll plan_roller_coaster(vector<int> s, vector<int> t) {
    map<int,int> corr;
    set<int> numbers;
    vector<int> vel;
    
    for(int i = 0; i < (int)s.size(); i++)
        numbers.insert(s[i]), numbers.insert(t[i]);
    
    for(auto it : numbers) {
        corr[it] = vel.size();
        vel.pb(it);
    }

    // corr[num] = pos
    // vel[pos] = num

    int n = vel.size();
    vector<int> in(n), out(n);

    for(int i = 0; i < n; i++)
        pai[i] = i, sz[i] = 1;

    for(int i = 0; i < (int)s.size(); i++) {
        int u = corr[s[i]], v = corr[t[i]];
        out[u]++;
        in[v]++;
        join(u,v);
    }

    join(0, n-1);
    in[0]++;
    out[n-1]++;
    
    ll ans = 0;
    vector<pii> edges;

    for(int i = 0; i < n-1; i++) {
        if(out[i] - in[i] > 0) {
            ans += (ll)(vel[i+1]-vel[i])*(ll)(out[i]-in[i]);
            out[i+1] += (out[i] - in[i]);
            in[i] = out[i];
            join(i, i+1);
        }
        else if(out[i] - in[i] < 0) {
            in[i+1] += in[i] - out[i];
            out[i] = in[i];
            join(i, i+1);
        }
        edges.pb({vel[i+1]-vel[i], i});
    }

    sort(all(edges));

    for(auto [cost, u] : edges) {
        if(find(u) != find(u+1)) 
            join(u,u+1), ans += cost;
    }

    return ans;
}

• Subtask 1: 11 / 11
• Subtask 2: 23 / 23
• Subtask 3: 30 / 30
• Subtask 4: 36 / 36