Submission #1231580

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231580		LIA	Roller Coaster Railroad (IOI16_railroad)	C++17	0 / 100	114 ms	14300 KiB

railroad

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector <int> p , sz;
    DSU (int n): p(n), sz(n ,1) { iota(p.begin() ,p.end() ,0); }
    int find (int x) { return x == p[x] ? x : p[x] = find(p[x]); }

    void unite (int a,int b) {
        a = find(a);
        b = find(b);
        if (a == b) return;
        if (sz[a] < sz[b]) swap(a ,b);
        p[b] = a;
        sz[a] += sz[b];
    }
};

long long plan_roller_coaster (vector <int> s,vector <int> t) {
    int n = s.size();
    const long long INF = 2000000005LL;
    vector <long long> v;
    v.reserve(2 * n + 2);
    v.push_back(1);
    for (int i = 0 ; i < n ; i++) {
        v.push_back(s[i]);
        v.push_back(t[i]);
    }
    v.push_back(INF);
    sort(v.begin() ,v.end());
    v.erase(unique(v.begin() ,v.end()) ,v.end());
    int m = v.size();
    auto id = [&] (long long x) { return int(lower_bound(v.begin() ,v.end() ,x) - v.begin()); };
    vector <long long> diff(m + 1 ,0);
    DSU dsu(m);
    vector <int> used;
    used.reserve(2 * n + 2);
    for (int i = 0 ; i < n ; i++) {
        int a = id(s[i]) , b = id(t[i]);
        used.push_back(a);
        used.push_back(b);
        dsu.unite(a ,b);
        if (t[i] > s[i]) {
            diff[a]++;
            diff[b]--;
        } else if (t[i] < s[i]) {
            diff[a]--;
            diff[b]++;
        }
    }
    int a = id(INF) , b = id(1LL);
    used.push_back(a);
    used.push_back(b);
    dsu.unite(a ,b);
    diff[a]--;
    diff[b]++;
    long long bal = 0;
    for (int i = 0 ; i < m - 1 ; i++) {
        bal += diff[i];
        if (bal) return 1;
    }
    int root = dsu.find(used[0]);
    for (int x : used) if (dsu.find(x) != root) return 1;
    return 0;
}

Compilation message (stderr)

railroad.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
railroad_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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