Submission #815846

#	Time	Username	Problem	Language	Result	Execution time	Memory
815846		math_rabbit_1028	Stations (IOI20_stations)	C++14	0 / 100	662 ms	8900 KiB

stations

#include "stations.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> adj[1010];
int ch[1010], ord[1010], par[1010];
vector<int> temp[1010], sub[1010];
int LCA[1010][1010];

int r = -1;
void DFS(int v) {
	ord[++r] = v;
	for (int i = 0; i < adj[v].size(); i++) {
		int next = adj[v][i];
		if (ch[next]) continue;
		ch[next] = 1;
		par[next] = v;
		DFS(next);
		temp[v].push_back(r);
	}
}


void setLCA(int v, int st, int l) {
	ch[v] = 1;
	LCA[st][v] = l;
	for (int i = 0; i < adj[v].size(); i++) {
		int next = adj[v][i];
		if (next == par[v]) continue;
		if (ch[next]) continue;
		setLCA(next, st, l);
	}
}
void getLCA(int v, int st) {
	if (v < 0) return;
	setLCA(v, st, v);
	getLCA(par[v], st);
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	for (int i = 0; i < n - 1; i++) {
		adj[u[i]].push_back(v[i]);
		adj[v[i]].push_back(u[i]);
	}

	for (int i = 0; i < n; i++) ch[i] = 0;
	par[0] = -1; ch[0] = 1;
	DFS(0);
	vector<int> lab(n);
	for (int i = 0; i < n; i++) lab[ord[i]] = i;
	for (int i = 0; i < n; i++) sub[i] = temp[ord[i]];

	for (int i = 0; i < n; i++) {
		for (int i = 0; i < n; i++) ch[i] = 0;
		getLCA(i, i);
	}

	//for (int i = 0; i < n; i++) cout << lab[i] << " ";
	//cout << "\n";

	return lab;
}

int find_next_station(int s, int t, vector<int> c) {
	if (LCA[s][t] == s) {
		int p = 0;
		if (c[0] < s) p++;
		for (int i = 0; i < sub[s].size(); i++) {
			if (sub[s][i] < t) p++;
			else break;
		}
		return c[p];
	}
	else return c[0];
}

Compilation message (stderr)

stations.cpp: In function 'void DFS(int)':
stations.cpp:13:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |  for (int i = 0; i < adj[v].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~
stations.cpp: In function 'void setLCA(int, int, int)':
stations.cpp:27:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |  for (int i = 0; i < adj[v].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:68:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |   for (int i = 0; i < sub[s].size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~

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