oj.uz

Submission #959288

# Submission time Handle Problem Language Result Execution time Memory
959288 2024-04-07T21:02:43 Z hyakup Roller Coaster Railroad (IOI16_railroad) C++17
0 / 100
 981 ms 524288 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12888 KB n = 2
2 Correct 4 ms 12888 KB n = 2
3 Correct 3 ms 12888 KB n = 2
4 Correct 4 ms 12892 KB n = 2
5 Correct 3 ms 12892 KB n = 2
6 Incorrect 4 ms 12892 KB answer is not correct: 1 instead of 523688153
7 Halted 0 ms 0 KB -

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12888 KB n = 2
2 Correct 4 ms 12888 KB n = 2
3 Correct 3 ms 12888 KB n = 2
4 Correct 4 ms 12892 KB n = 2
5 Correct 3 ms 12892 KB n = 2
6 Incorrect 4 ms 12892 KB answer is not correct: 1 instead of 523688153
7 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 981 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12888 KB n = 2
2 Correct 4 ms 12888 KB n = 2
3 Correct 3 ms 12888 KB n = 2
4 Correct 4 ms 12892 KB n = 2
5 Correct 3 ms 12892 KB n = 2
6 Incorrect 4 ms 12892 KB answer is not correct: 1 instead of 523688153
7 Halted 0 ms 0 KB -