Submission #1013638

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013638		ProtonDecay314	Roller Coaster Railroad (IOI16_railroad)	C++17	30 / 100	147 ms	18964 KiB

railroad

/* AM+DG */

/*
For subtask 3, consider, for each rail, the prefix it can reach

4 2 1 0 -> doesn't work
3 1 1 1

4 2 2 0 -> works
3 2 1 1

4 3 1 0 -> works

4 2 1 1 -> doesn't work

2 2 4 0 -> doesn't work

The cost of a placement is.. hmm

max(t[i] - s[i + 1], 0) + max(t[i - 1] - s[i], 0) -> if separated more than two apart

t[i] t[i + 1] t[i + 2] t[i + 3]
s[i] s[i + 1] s[i + 2] s[i + 3]

c = max(t[i] - s[i + 1], 0) + max(t[i + 1] - s[i + 2], 0) + max(t[i + 2] - s[i + 3], 0)
c' = max(t[i] - s[i + 2], 0) + max(t[i + 2] - s[i + 1], 0) + max(t[i + 1] - s[i + 3], 0)

4
NULL -> 5
1 7 -> 1
4 3 -> 4
5 8 -> 1
6 6 -> 2
INF -> 0

s[i] t[i]
s[j] t[j]

max(t[i] - s[j], 0)

s[i] t[i] s[j] t[j] -> 0
s[i] t[i] t[j] s[j] -> 0
s[i] s[j] t[i] t[j] -> t[i] - s[j]
s[i] s[j] t[j] t[i] -> 
s[i] t[j] t[i] s[j]
s[i] t[j] s[j] t[i]

t[i] s[i] s[j] t[j]
t[i] s[i] t[j] s[j]
s[j] s[i] t[i] t[j]
s[j] s[i] t[j] t[i]
t[j] s[i] t[i] s[j]
t[j] s[i] s[j] t[i]

t[i] s[j] s[i] t[j]
t[i] t[j] s[i] s[j]
s[j] t[i] s[i] t[j]
s[j] t[j] s[i] t[i]
t[j] t[i] s[i] s[j]
t[j] s[j] s[i] t[i]

t[i] s[j] t[j] s[i]
t[i] t[j] s[j] s[i]
s[j] t[i] t[j] s[i]
s[j] t[j] t[i] s[i]
t[j] t[i] s[j] s[i]
t[j] s[j] t[i] s[i]

possible to do with 0:

is there a permutation of s and t s.t t[i] <= s[i + 1]


1 5 4 3 1 6

0 -> 0
1 -> 0, 1, 2, 3, 4
2 -> 0, 1, 2, 3
3 -> 0, 1, 2
4 -> 0
5 -> 0, 1, 2, 3, 4, 5, 6

0 -> 0
1 -> 0, 1, 2
2 -> 0, 1, 2
3 -> 0, 1, 2, 3
4 -> 0
5 -> 0, 1, 2, 3, 4, 5, 6
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
typedef vector<vpi> vvpi;
typedef vector<vpll> vvpll;
typedef vector<bool> vb;
#define IOS ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define L(varll, mn, mx) for(ll varll = (mn); varll < (mx); varll++)
#define LR(varll, mx, mn) for(ll varll = (mx); varll > (mn); varll--)
#define LI(vari, mn, mx) for(int vari = (mn); vari < (mx); vari++)
#define LIR(vari, mx, mn) for(int vari = (mx); vari > (mn); vari--)
#define INPV(varvec) for(auto& varveci : (varvec)) cin >> varveci
#define fi first
#define se second
#define pb push_back
#define INF(type) numeric_limits<type>::max()
#define NINF(type) numeric_limits<type>::min()
#define TCASES int t; cin >> t; while(t--)

class UF {
    public:
        vi par;
        vi csize;
        int n;
        int comps;
        
        UF(int a_n): n(a_n), par(a_n, 0), csize(a_n, 1), comps(a_n) {
            LI(i, 0, n) {
                par[i] = i;
            }
        }

        int find(int i) {
            while(i != par[i]) {
                par[i] = par[par[i]];
                i = par[i];
            }

            return i;
        }

        bool conn(int i, int j) {
            return find(i) == find(j);
        }

        void unify(int i, int j) {
            int pi = find(i), pj = find(j);

            if(pi == pj) return;

            int& is = csize[pi];
            int& js = csize[pj];

            if(is < js) {
                par[pi] = pj; // ! Careful, you set this to par[i] = j, are you fine???
                js += is;
            } else {
                par[pj] = pi;
                is += js;
            }

            comps--;

            #ifdef DEBUG
            cout << "NCOMPS: " << comps << " " << pi << " " << pj << endl;
            #endif
        }
};

ll plan_roller_coaster(vi s, vi t) {
    s.push_back(INF(int));
    t.push_back(0);
    ll n = s.size();

    vpi pts;

    // Creating a list of entry and exit points
    LI(i, 0, n) {
        pts.push_back({s[i], 1});
        pts.push_back({t[i], -1});
    }

    sort(pts.begin(), pts.end());

    // Make a UFDS here

    UF uf((n) << 1);

    int cur_depth = 0;

    ll ans = 0ll;

    LI(i, 0, ((n) << 1) - 1) {
        auto [ccoord, change] = pts[i];


        auto ncoord = pts[i + 1].fi;
        #ifdef DEBUG
        cout << "POINT " << i + 1 << ": " << ncoord << endl;
        #endif

        cur_depth += change;

        if(ccoord != ncoord) {
            // The next coordinate is different! Process the current coordinate

            if(cur_depth >= 1) {
                ans += (ll)(cur_depth) * (ll)(ncoord - ccoord);
            }

            // If may connector rail, unify the components, haha
            if(cur_depth != 0) {
                uf.unify(i, i + 1);
            }
        } else {
            uf.unify(i, i + 1);
        }
        // Otherwise, nothing much to do here, carry on with your jinsei, hito-san! :D
    }

    vector<pair<int, pi>> e;

    #ifdef DEBUG
    cout << "BASE ANS: " << ans << endl;
    #endif

    // Unify vertices pointed by railroads
    LI(i, 0, (n) << 1) {
        int v1 = s[i], v2 = t[i];

        int l1, r1;

        int l = -1, r = (n) << 1;

        while(r - l > 1) {
            int m = (l + r) >> 1;

            if(v1 <= pts[m].fi) r = m;
            else l = m;
        }

        l1 = r;

        l = -1; r = (n) << 1;

        while(r - l > 1) {
            int m = (l + r) >> 1;

            if(v2 <= pts[m].fi) r = m;
            else l = m;
        }

        r1 = r;

        uf.unify(l1, r1);
    }

    LI(i, 0, ((n) << 1) - 1) {
        if(!uf.conn(i, i + 1)) {
            e.push_back({pts[i + 1].fi - pts[i].fi, {uf.find(i), uf.find(i + 1)}});

            #ifdef DEBUG
            cout << pts[i + 1].fi - pts[i].fi << " " << uf.find(i) << " " << uf.find(i + 1) << endl;
            #endif
        }
        #ifdef DEBUG
        // cout << pts[i].fi << " " << uf.find(i) << endl;
        #endif
    }

    sort(e.begin(), e.end());

    // Kruskal's Time wahoo!! :D

    int cur_e_ind = 0;
    while(uf.comps > 1) {
        auto [weight, vertices] = e[cur_e_ind];
        auto [i, j] = vertices;

        if(i != j) {
            uf.unify(i, j);
            ans += (ll)weight;
            #ifdef DEBUG
            cout << "Added " << weight << endl;
            #endif
        }

        cur_e_ind++;
    }

    return ans;
}

#ifdef DEBUG
int main() {
    int n;
    cin >> n;

    vi s(n, 0);
    vi t(n, 0);

    LI(i, 0, n) {
        cin >> s[i] >> t[i];
    }

    cout << plan_roller_coaster(s, t) << endl;
}
#endif

Compilation message (stderr)

railroad.cpp: In constructor 'UF::UF(int)':
railroad.cpp:121:13: warning: 'UF::n' will be initialized after [-Wreorder]
  121 |         int n;
      |             ^
railroad.cpp:119:12: warning:   'vi UF::par' [-Wreorder]
  119 |         vi par;
      |            ^~~
railroad.cpp:124:9: warning:   when initialized here [-Wreorder]
  124 |         UF(int a_n): n(a_n), par(a_n, 0), csize(a_n, 1), comps(a_n) {
      |         ^~

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