Submission #835939

#	Time	Username	Problem	Language	Result	Execution time	Memory
835939		JustAmethyst	Stations (IOI20_stations)	C++17	0 / 100	732 ms	668 KiB

stations

#include "stations.h"
#include <bits/stdc++.h>
#define sz(x) (int)(x.size())
using namespace std;

const int N = 1000;
vector<int> edges[N];
vector<int> tin(N), tout(N);
int t1, t2;

void dfs(int x, int p) {
	int y;
	tin[x] = t1;
	++t1;

	while (!edges[x].empty()) {
		y = edges[x].back();
		edges[x].pop_back();
		if (y != p) {
			dfs(y, x);
		}
	}
	tout[x] = t2;
	++t2;
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	vector<int> codes(n);
	t1 = 0, t2 = 0;

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

	dfs(0, -1);
	for (int i = 0; i < n; ++i) {
		// cout << sz(edges[i]) << "\n";
		codes[i] = tin[i]*1000 + tout[i];
	}
	return codes;
}

int find_next_station(int s, int e, vector<int> c) {
	int sin = s/1000; //, sout = s % 1000;
	int ein = e/1000, eout = e % 1000;
	if (ein < sin) {
		for (int x : c) {
			if ((x/1000) <= sin) {
				return x;
			}
		}
	}
	for (int x : c) {
		if ((x/1000) > sin && (x/1000) <= ein && (x%1000) >= eout) {
			return x;
		}
	}

	return -1;
}

// void solve() {
// 	vector<int> labels = label(3, 1000000000, {2, 2}, {1, 0});
// 	// for (auto x : labels) {
// 	// 	cout << x << " ";
// 	// 	cout << "\n";
// 	// }
// 	// cout << "\n";

// 	// cout << find_next_station(labels[1], labels[0], {labels[2]}) << "\n";
// 	// cout << find_next_station(labels[1], labels[2], {labels[2]}) << "\n";
// 	// cout << find_next_station(labels[2], labels[1], {labels[0], labels[1]}) << "\n";
// 	// cout << find_next_station(labels[0], labels[2], {labels[2]}) << "\n";
// 	// cout << find_next_station(labels[2], labels[0], {labels[0], labels[1]}) << "\n";
// 	// cout << find_next_station(labels[0], labels[1], {labels[2]}) << "\n";

// 	// cout << "\n";
// 	// cout << find_next_station(1003, 4001, {2000, 3002, 4}) << "\n";
// }

// int main() {
// 	ios_base::sync_with_stdio(0);
// 	cin.tie(0);
// 	// int t;
// 	// cin >> t;
// 	// while (t--) 
// 	solve();
	
// 	return 0;
// }


// 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() {
// 	assert(scanf("%d", &r) == 1);
// 	for (int tc = 0; tc < r; tc++) {
// 		assert(scanf("%d%d", &n, &k) == 2);
// 		u.resize(n - 1);
// 		v.resize(n - 1);
// 		adjlist.clear();
// 		adjlist.resize(n);
// 		for (int i = 0; i < n - 1; i++) {
// 			assert(scanf("%d%d", &u[i], &v[i]) == 2);
// 			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];
// 			}
// 		}
// 		assert(scanf("%d", &q) == 1);
// 		for (int i = 0; i < q; i++) {
// 			assert(scanf("%d%d%d", &s, &t, &w) == 3);
// 			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);
// }

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