Submission #744714

#	Time	Username	Problem	Language	Result	Execution time	Memory
744714		josanneo22	Stations (IOI20_stations)	C++17	0 / 100	3135 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 <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;
	}
	for (int i = 0; i < n - 1; i++) {
		u[i]--; v[i]--;
		Add(u[i], v[i]);
		Add(v[i], u[i]);
	}
	Dfs(0);
	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])//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];
			}
		}
	}
}

Compilation message (stderr)

stations.cpp: In function 'void Dfs(int)':
stations.cpp:30:26: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   30 |  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