Submission #432890

#	Time	Username	Problem	Language	Result	Execution time	Memory
432890		lior5654	Stations (IOI20_stations)	C++17	31.04 / 100	981 ms	764 KiB

stations

#include <bits/stdc++.h>

using namespace std;


typedef long long int ll;
typedef pair<ll, ll> pl;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pl> vpl;
typedef vector<vpl> vvpl;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pi> vpi;
typedef vector<vpi> vvpi;

#define rep(i, n) for(int i = 0; i < n; ++i)
#define all(c) (c.begin()), (c.end())
#define pb push_back
#define eb emplace_back
#define fi first
#define se second


#include "stations.h"


const int maxn = 1e3 + 5;


vi g[maxn];
int st[maxn]; int en[maxn]; int dt = -1;

void dfs(int c, int p=-1) {
	st[c] = ++dt; 
	for(auto e  : g[c]) {
		if(e!=p) {
			dfs(e, c);
		}
	}
	en[c] = ++dt;
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {

	rep(i, n-1) {
		g[u[i]].pb(v[i]); g[v[i]].pb(u[i]);
	}
	dfs(0);
	vi res(n);
	rep(i, n) {
		res[i] = 2000*en[i] + st[i];
	}
	/*cout << "debug" << endl;
	rep(i, n) {
		cout << st[i] << ' '<< en[i] << endl;
	}
	for(auto e : res) {
		cout << e << ' ';
	}
	cout << endl;
	*/
	rep(i, n) {
		g[i].clear(); st[i] = 0; en[i] = 0;
	}
	dt = -1;
	return res;
}

int find_next_station(int s, int t, std::vector<int> c) {
	int s_st = s % 2000;
	int t_st = t % 2000;
	int s_en = s / 2000;
	int t_en = t / 2000;
	vi childs;
	int best = 0;
	for(int i = 1; i < c.size(); ++i) {
		if(c[i] % 2000 < c[best] % 2000) {
			best = i;
		}
	}
	int papa_label = c[best];
	int papa_st = papa_label % 2000;
	int papa_en = papa_label / 2000;
	if(papa_st < s_st) { // there's a papa
		for(auto e : c) {
			if(e != papa_label) {
				childs.pb(e);
			}
		}
	} else { // there's no papa
		for(auto e : c) {
			childs.pb(e);
		}
	}
	if(papa_st < s_st) {
		if(t_st > s_en || t_st < s_st) {
			return papa_label;
		}
	}
	sort(all(childs), [&](int xx, int yy) {
		return xx % 2000 < yy % 2000;
	});
	// find the first child whose end time is bigger than or equal to t's start time
	for(int i = 0; i < childs.size(); ++i) {
		if(childs[i] / 2000 >= t_st) return childs[i];
	}
	
	assert(false);
}

Compilation message (stderr)

stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:77:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |  for(int i = 1; i < c.size(); ++i) {
      |                 ~~^~~~~~~~~~
stations.cpp:105:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |  for(int i = 0; i < childs.size(); ++i) {
      |                 ~~^~~~~~~~~~~~~~~
stations.cpp:74:6: warning: unused variable 't_en' [-Wunused-variable]
   74 |  int t_en = t / 2000;
      |      ^~~~
stations.cpp:84:6: warning: unused variable 'papa_en' [-Wunused-variable]
   84 |  int papa_en = papa_label / 2000;
      |      ^~~~~~~

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