Submission #622870

#	Time	Username	Problem	Language	Result	Execution time	Memory
622870		yanndev	Stations (IOI20_stations)	C++17	10 / 100	890 ms	604 KiB

stations

#include "stations.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;

const int MX = 1042;

int in[MX];
int out[MX];
int dfsT = 0;
vector<int> adj[MX];

void dfs(int node, int par) {
	//cout << "cur " << node << '\n';
	in[node] = dfsT++;
	for (auto& x: adj[node])
		if (x != par)
			dfs(x, node);
	out[node] = dfsT++;
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	//cout << "called\n";
	vector<int> labels(n);

	for (int i = 0; i < n; i++)
		adj[i].clear();

	for (int i = 0; i + 1 < n; i++) {
		adj[u[i]].push_back(v[i]);
		adj[v[i]].push_back(u[i]);
	}

	dfs(0, -1);

	for (int i = 0; i < n; i++)
		labels[i] = in[i] * 2000 + out[i];
	return labels;
}

int find_next_station(int s, int t, vector<int> c) {
	vector<pair<int, int>> times {};

	int sIn = s / 2000;
	int sOut = s % 2000;
	int tIn = t / 2000;
	int tOut = t % 2000;

	for (auto& x: c)
		times.push_back({x / 2000, x % 2000});
	
	int par = -1;
	for (auto& x: times) {
		if (sIn <= x.fi) {
			if (x.fi <= tIn && tOut <= x.se)
				return x.fi * 2000 + x.se;
		} else {
			par = x.fi * 2000 + x.se;
		}
	}

	return par;
}

Compilation message (stderr)

stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:46:6: warning: unused variable 'sOut' [-Wunused-variable]
   46 |  int sOut = s % 2000;
      |      ^~~~

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