Submission #744705

#	Time	Username	Problem	Language	Result	Execution time	Memory
744705		josanneo22	Stations (IOI20_stations)	C++17	0 / 100	3143 ms	2097152 KiB

stations

#include <bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
#include<algorithm>
using namespace std;

#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second 

#include "stations.h"
#include <vector>
const int N = 1005;

struct Edge {
	int next, t;
}e[N << 1];
int head[N], edc;

void Add(int x, int y) {
	e[++edc] = { head[x], y };
	head[x] = edc;
}

int f[20][N], dep[N];

void Dfs(int x) {
	dep[x] = dep[f[0][x]] + 1;
	for (int i = 0; (1 << i + 1) <= dep[x]; ++i)
		f[i + 1][x] = f[i][f[i][x]];
	for (int i = head[x]; i; i = e[i].next) {
		int y = e[i].t;
		if (y == f[0][x]) continue;
		f[0][y] = x;
		Dfs(y);
	}
}

int Lca(int x, int y) {
	if (dep[x] < dep[y]) std::swap(x, y);
	for (int k = dep[x] - dep[y], i = 0; k; k >>= 1, ++i)
		if (k & 1) x = f[i][x];
	if (x == y) return x;
	for (int i = 19; i >= 0; --i)
		if (f[i][x] != f[i][y])
			x = f[i][x], y = f[i][y];
	return f[0][x];
}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	std::vector<int> labels(n);
	for (int i = 0; i < n; i++) {
		labels[i] = i+1;
	}
	for (int i = 0; i < n - 1; i++) {
		Add(u[i], v[i]);
		Add(v[i], u[i]);
	}
	Dfs(1);
	return labels;
}
int find_next_station(int s, int t, std::vector<int> c) {
	//checking for direct link in logn
	auto it = lower_bound(c.begin(), c.end(), t);
	if (it != c.end() && c[it - c.begin()] == t) return t;
	/*
		move up from u to lca(u,v) until lca(u,v)==u
		if v is lower: move to v by moving towards lca(next,v)=next
		else lca(u,v) is v: just move up such that depth[next]==depth[u]-1
	*/
	int save = Lca(s, t);
	if (save != t && save != s) {//different node just move towards it
		for (int i = 0; i < c.size(); i++) {
			if (dep[c[i]] < dep[s] && Lca(c[i],t)==save)//move upwards
			{
				return c[i];
			}
		}
	}
	else if (save == s) {//now reached lca(u,v) and u is heigher, move down to v
		for (int i = 0; i < c.size(); i++) {
			if (Lca(c[i], t) == c[i] && dep[c[i]] > dep[s]) {
				return c[i];
			}
		}
	}
	else if(save==t){//t is heigher
		for (int i = 0; i < c.size(); i++) {
			if (Lca(c[i], s) == c[i] && dep[c[i]] > dep[t]) {
				return c[i];
			}
		}
	}
}
/*

#include <cstdio>
#include <cassert>
#include <map>
#include <vector>
#include <algorithm>

static int max_label = 0;
static int r, n, k, q;
static std::vector<int> u, v, labels, answers;
static std::map<int, int> reverse_labels;
static std::vector<std::vector<int>> adjlist;
static int s, t, w;
static std::vector<int> c;

int main() {
	cin >> r;
	for (int tc = 0; tc < r; tc++) {
		cin >> n >> k;
		u.resize(n - 1);
		v.resize(n - 1);
		adjlist.clear();
		adjlist.resize(n);
		for (int i = 0; i < n - 1; i++) {
			cin >> u[i] >> v[i];
			adjlist[u[i]].push_back(v[i]);
			adjlist[v[i]].push_back(u[i]);
		}
		labels = label(n, k, u, v);
		if ((int)labels.size() != n) {
			printf("Number of labels not equal to %d\n", n);
			exit(0);
		}
		reverse_labels.clear();
		for (int i = 0; i < n; i++) {
			if (labels[i] < 0 || labels[i] > k) {
				printf("Label not in range 0 to %d\n", k);
				exit(0);
			}
			if (reverse_labels.find(labels[i]) != reverse_labels.end()) {
				printf("Labels not unique\n");
				exit(0);
			}
			reverse_labels[labels[i]] = i;
			if (labels[i] > max_label) {
				max_label = labels[i];
			}
		}
		cin >> q;
		for (int i = 0; i < q; i++) {
			cin >> s >> t >> w;
			c.clear();
			for (int v : adjlist[s]) {
				c.push_back(labels[v]);
			}
			std::sort(c.begin(), c.end());
			int answer = find_next_station(labels[s], labels[t], c);
			if (!std::binary_search(c.begin(), c.end(), answer)) {
				printf("Label %d returned by find_next_station not found in c\n", answer);
				exit(0);
			}
			answers.push_back(reverse_labels[answer]);
		}
	}
	printf("%d\n", max_label);
	for (int index : answers) {
		printf("%d\n", index);
	}
	exit(0);
}*/

Compilation message (stderr)

stations.cpp: In function 'void Dfs(int)':
stations.cpp:31:26: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   31 |  for (int i = 0; (1 << i + 1) <= dep[x]; ++i)
      |                        ~~^~~
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:75:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |   for (int i = 0; i < c.size(); i++) {
      |                   ~~^~~~~~~~~~
stations.cpp:83:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |   for (int i = 0; i < c.size(); i++) {
      |                   ~~^~~~~~~~~~
stations.cpp:90:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |   for (int i = 0; i < c.size(); i++) {
      |                   ~~^~~~~~~~~~
stations.cpp:96:1: warning: control reaches end of non-void function [-Wreturn-type]
   96 | }
      | ^

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