Submission #1051490

#	Time	Username	Problem	Language	Result	Execution time	Memory
1051490		aykhn	Stations (IOI20_stations)	C++17	67.23 / 100	544 ms	1048 KiB

stations

#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
 
const int MAX = 1005;
vector<int> g[MAX];	
int in[MAX], out[MAX];
int col[MAX];
int t = 0;
void dfs(int node, int p){
	col[node] = col[p] ^ 1;
	in[node] = t++;
	for(int to : g[node]){
		if(to == p) continue;
		dfs(to, node);
	}
	out[node] = t++;
}
 
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	for(int i = 0; i < n; i++) g[i].clear();
	for(int i = 0; i < n - 1; i++){
		g[u[i]].push_back(v[i]);
		g[v[i]].push_back(u[i]);
	}
	dfs(1, 1);
	vector<int> L;
	for(int i = 0; i < n; i++){
		if(col[i]) L.push_back(in[i]);
		else L.push_back(out[i]); 
	}
	return L;
}
 
int find_next_station(int s, int t, vector<int> c) {
	sort(c.begin(), c.end());
	if(s < c[0]){
		int in = s + 1;
		for(int i = 0; i < c.size() - 1; i++){
			if(in <= t && t <= c[i]){
				return c[i];
			}
			in = c[i] + 1;
		}
		return c.back();
	}
	else{
		sort(c.rbegin(), c.rend());
		int out = s - 1;
		for(int i = 0; i < c.size() - 1; i++){
			if(c[i] <= t && t <= out) return c[i];
			out = c[i] - 1;
		}
		return c.back();
	}
}

Compilation message (stderr)

stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:39:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |   for(int i = 0; i < c.size() - 1; i++){
      |                  ~~^~~~~~~~~~~~~~
stations.cpp:50:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |   for(int i = 0; i < c.size() - 1; i++){
      |                  ~~^~~~~~~~~~~~~~

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