Submission #1021152

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021152		kachim2	Stations (IOI20_stations)	C++17	0 / 100	581 ms	1000 KiB

stations

#include "stations.h"
#include <vector>
#include <iostream>
#include <climits>
#include <algorithm>
using namespace std;
int dfs(vector<int> &labels, vector<vector<int>> &tree, int v, int p, int pre, int d){
	if(d&1)
		labels[v] = pre;
	for(auto i : tree[v]){
		if(i!=p){
			pre = dfs(labels, tree, i, v, pre+1, d+1);
		}
	}
	if(!(d&1))
		labels[v] = pre;
	return pre+1;
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	std::vector<int> labels(n);
	vector<vector<int>> tree(n);
	for(int i = 0; i < u.size(); i++){
		tree[u[i]].push_back(v[i]);
		tree[v[i]].push_back(u[i]);
	}
	dfs(labels, tree, 0, -1, 0, 0);
	vector<pair<int, int>> labx(n);
	for(int i = 0; i < n; i++){
		labx[i] = {labels[i], i};
	}
	sort(labx.begin(), labx.end());
	for(int i = 0; i < n; i++){
		labels[labx[i].second] = i;
	}
	std::cerr << "LOG ";
	for(auto i : labels) std::cerr << i << ' ';
	std::cerr << "\n";
	return labels;
}

int find_next_station(int s, int t, std::vector<int> c) {

	for(auto i : c) if(i == t) return t;
	vector<int> pre(c.size()-1), post(c.size()-1);
	sort(c.begin(), c.end());
	int minn = INT_MAX, parent = 0;
	for(auto i : c) minn = min(i, minn);
	if(minn < s){
		parent = c[0];
		c.erase(c.begin());
		for(int i = 0; i < c.size(); i++) pre[i] = c[i];
		post.back() = s-1;
		for(int i = 0; i < c.size()-1; i++){
			post[i] = pre[i+1]-1;
		}
	}else{
		parent = c.back();
		c.pop_back();
		for(int i = 0; i < c.size(); i++) post[i] = c[i];
		pre[0] = s+1;
		for(int i = 1; i < c.size(); i++){
			pre[i] = post[i-1];
		}
	}
	cerr <<"S: " << s << " T: " << t << "\nPRE: ";
	for(auto i : pre) cerr << i << ' ';
	cerr << "\nPOST: ";
	for(auto i : post) cerr << i << ' ';
	cerr << '\n';
	for(int i = 0; i < c.size(); i++){
		if(t>=pre[i] && t <= post[i]) parent = c[i];
	}
	return parent;
}	

Compilation message (stderr)

stations.cpp: In function 'std::vector<int> label(int, int, std::vector<int>, std::vector<int>)':
stations.cpp:22:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |  for(int i = 0; i < u.size(); i++){
      |                 ~~^~~~~~~~~~
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:51:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |   for(int i = 0; i < c.size(); i++) pre[i] = c[i];
      |                  ~~^~~~~~~~~~
stations.cpp:53:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |   for(int i = 0; i < c.size()-1; i++){
      |                  ~~^~~~~~~~~~~~
stations.cpp:59:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |   for(int i = 0; i < c.size(); i++) post[i] = c[i];
      |                  ~~^~~~~~~~~~
stations.cpp:61:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |   for(int i = 1; i < c.size(); i++){
      |                  ~~^~~~~~~~~~
stations.cpp:70:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |  for(int i = 0; i < c.size(); i++){
      |                 ~~^~~~~~~~~~

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