Submission #108235

#	Time	Username	Problem	Language	Result	Execution time	Memory
108235		tictaccat	Roller Coaster Railroad (IOI16_railroad)	C++14	0 / 100	266 ms	23760 KiB

railroad

#include "railroad.h"

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

const ll INF = 1e18;

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {

    int n = (int) s.size();

    vector<int> bin;
    for (int i = 0; i < n; i++) {
        bin.push_back(s[i]);
        bin.push_back(t[i]);
    }

    sort(bin.begin(),bin.end());
    bin.erase(unique(bin.begin(),bin.end()),bin.end());

    int K = bin.size();

    vector<vector<int>> in(K); vector<int> out(K);

    for (int i = 0; i < n; i++) {
        int u = lower_bound(bin.begin(),bin.end(),t[i])-bin.begin(); int v = lower_bound(bin.begin(),bin.end(),s[i])-bin.begin();
        assert(u < K && v < K);
        in[u].push_back(v); out[v]++;
    }

    int a = 0, b = 0, c = 0;

    for (int u = 0; u < K; u++) {
        int deg = in[u].size() - out[u];
        if (deg == 1) a++;
        else if (deg == -1) b++;
        else if (deg != 0) c++;
    }

   // cout << a << " " << b << " " << c << "\n";

    if (a == 1 && b == 1 && c == 0) return 0;

    // vector<int> res;

    // while (!st.empty()) {
    //     for (int )
    // }

    return 1;
}

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