Submission #1080040

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080040		KaleemRazaSyed	Stations (IOI20_stations)	C++17	10 / 100	622 ms	800 KiB

stations

#include<bits/stdc++.h>
#include "stations.h"

using namespace std;

const int N = 1005;
vector<int> G[N];
int in[N], out[N];
int emit = 0;

void add_edge(int x, int y)
{
  G[x].push_back(y);
  G[y].push_back(x);
}

void dfs(int v, int p = -1)
{
  // cerr << v << endl;
  in[v] = emit++;
  for(int u : G[v])
    if(u != p)
      dfs(u, v);
  out[v] = emit;
}

vector<int> label(int n, int k, vector<int> u, vector<int> v)
{
  for(int i = 0; i < n; i ++)
    G[i].clear();
  
  for(int i = 0; i < u.size(); i ++)
    add_edge(u[i], v[i]);

  dfs(0);
  
  vector<int> l(n);
  for(int i = 0; i < n; i ++)
    {
      l[i] = in[i] * N + out[i];
      assert(out[i] < N);
    }
  return l;
}

int find_next_station(int s, int t, vector<int> c)
{
  int ins = s / N, outs = s % N;
  int in_t = t / N, outt = t % N;
  
  int p = -1;
  for(int i : c)
    {
      
      int ini = i / N, outi = i % N;
      if(ini <= ins && outs <= outi)
	{
	  p = i;
	  continue;
	}
      
      if(ini <= in_t && outt <= outi)
	return i;
    }
  assert(p != -1);
  return p;
}

Compilation message (stderr)

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

• Subtask 1: 0 / 5
• Subtask 2: 0 / 8
• Subtask 3: 0 / 16
• Subtask 4: 10 / 10
• Subtask 5: 0 / 61