Submission #1021335

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021335		Wansur	Roller Coaster Railroad (IOI16_railroad)	C++14	30 / 100	570 ms	72556 KiB

railroad

#include <bits/stdc++.h>
#define ent '\n'

typedef long long ll;
using namespace std;
const int maxn = 1e6+12;

vector<int> g[maxn];
int pref[maxn];
bool used[maxn];
int n, m;

void dfs(int v){
    used[v] = 1;
    for(int to:g[v]){
        if(!used[to]){
            dfs(to);
        }
    }
}

long long plan_roller_coaster(vector<int> s, vector<int> t){
    n = s.size();
    vector<int> uni = {1, (int)1e9+1};
    map<int, int> val;
    for(int x:s){
        uni.push_back(x);
    }
    for(int x:t){
        uni.push_back(x);
    }
    sort(uni.begin(), uni.end());
    uni.resize(unique(uni.begin(), uni.end()) - uni.begin());
    for(int i=0;i<uni.size();i++){
        val[uni[i]] = i + 1;
    }
    m = uni.size();
    for(int i=0;i<n;i++){
        s[i] = val[s[i]];
        t[i] = val[t[i]];
        if(s[i] > t[i]){
            pref[t[i]]--, pref[s[i]]++;
        }
        else{
            pref[s[i]]++, pref[t[i]]--;
        }
        g[s[i]].push_back(t[i]);
    }
    pref[1]--, pref[m]++;
    for(int i=1;i<m;i++){
        pref[i] += pref[i-1];
        if(pref[i] > 0){
            return 1;
        }
        if(pref[i] < 0){
            g[i].push_back(i+1);
        }
    }
    g[1].push_back(m);
    dfs(1);
    for(int i=1;i<=m;i++){
        if(!used[i]){
            return 1;
        }
    }
    return 0;
}

Compilation message (stderr)

railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:34:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for(int i=0;i<uni.size();i++){
      |                 ~^~~~~~~~~~~

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