Submission #959288

#	Time	Username	Problem	Language	Result	Execution time	Memory
959288		hyakup	Roller Coaster Railroad (IOI16_railroad)	C++17	0 / 100	981 ms	524288 KiB

railroad

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

const ll inf = 1e9 + 10;
const int maxn = 4e5 + 10;
vector<pair<int, int>> adj[maxn], aux;
vector<int> marc( maxn ), g( maxn );

void dfs( int cur ){
  while( !adj[cur].empty() ){
    auto [viz, id] = adj[cur].back(); adj[cur].pop_back();
    marc[id] = true;
    dfs( viz );
  }
}

ll plan_roller_coaster( vector<int> ini, vector<int> fim ){
    int n = ini.size();
    for( int i = 0; i < n; i++ ){ aux.push_back({ ini[i], i + 1 }); aux.push_back({ fim[i], -(i + 1) }); }
    aux.push_back({ 0, 0 });
    sort( aux.begin(), aux.end());
    int cont = 0;
    for( int i = 1; i < aux.size(); i++ ){
      auto [val, id] = aux[i]; 
      if( aux[i - 1].first != val ) cont++;
      if( id > 0 ) ini[id - 1] = cont;
      else fim[-id - 1] = cont;
    }

    for( int i = 0; i < n; i++ ){ adj[ini[i]].push_back({fim[i], i}); g[ini[i]]++; g[fim[i]]--; }
    adj[0].push_back({1, n}); g[1]--;
    for( int i = 1; i <= cont; i++ ){
      while( g[i] < 0 ){
        adj[i].push_back({ i + 1, n });
        g[i]++; g[i + 1]--;
      }
      if( g[i] > 0 ) return 1;
    }
    dfs(0);
    for( int i = 0; i < n; i++ ) if( marc[i] == 0 ) 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:25:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for( int i = 1; i < aux.size(); i++ ){
      |                     ~~^~~~~~~~~~~~

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