Submission #124701

#	Time	Username	Problem	Language	Result	Execution time	Memory
124701		zubec	Roller Coaster Railroad (IOI16_railroad)	C++14	30 / 100	395 ms	45524 KiB

railroad

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

const int N = 400100;

vector <int> g[N];

bool used[N];

void dfs(int v){
    used[v] = 1;
    for (int i = 0; i < g[v].size(); i++){
        int to = g[v][i];
        if (!used[to])
            dfs(to);
    }
}

int dp[N];

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
    vector <int> zhat;
    s.push_back(1e9);
    t.push_back(1);
    for (int i = 0; i < s.size(); i++){
        zhat.push_back(s[i]);
        zhat.push_back(t[i]);
    }
    sort(zhat.begin(), zhat.end());
    zhat.erase(unique(zhat.begin(), zhat.end()), zhat.end());
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i < s.size(); i++){
        int ss = lower_bound(zhat.begin(), zhat.end(), s[i])-zhat.begin();
        int tt = lower_bound(zhat.begin(), zhat.end(), t[i])-zhat.begin();
        --dp[ss];
        ++dp[tt];
        g[ss].push_back(tt);
    }
    int cur = 0;
    for (int i = 0; i < zhat.size(); i++){
        if (cur > 0 && i > 0){
            g[i-1].push_back(i);
        }
        cur += dp[i];
        if (cur < 0)
            return 123;
    }
    memset(used, 0, sizeof(used));
    dfs(0);
    for (int i = 0; i < zhat.size(); i++)
        if (!used[i])
            return 123;
    return 0;

}

Compilation message (stderr)

railroad.cpp: In function 'void dfs(int)':
railroad.cpp:15:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[v].size(); i++){
                     ~~^~~~~~~~~~~~~
railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:28:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < s.size(); i++){
                     ~~^~~~~~~~~~
railroad.cpp:35:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < s.size(); i++){
                     ~~^~~~~~~~~~
railroad.cpp:43:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < zhat.size(); i++){
                     ~~^~~~~~~~~~~~~
railroad.cpp:53:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < zhat.size(); i++)
                     ~~^~~~~~~~~~~~~

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