Submission #500196

#	Time	Username	Problem	Language	Result	Execution time	Memory
500196		benson1029	Stations (IOI20_stations)	C++14	100 / 100	913 ms	836 KiB

stations

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

int timer = 0;
int st[1005], ed[1005], dep[1005];
vector<int> edg[1005];
vector<int> ans;
vector< pair<int,int> > tmp;

void dfs(int x, int p) {
	if(x==0) dep[x] = 0;
	else dep[x] = dep[p]+1;
	st[x] = ++timer;
	for(int i:edg[x]) {
		if(i!=p) {
			dfs(i, x);
		}
	}
	ed[x] = ++timer;
}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	for(int i=0; i<n; i++) edg[i].clear();
	for(int i=0; i<n-1; i++) {
		edg[u[i]].push_back(v[i]);
		edg[v[i]].push_back(u[i]);
	}
	dfs(0, -1);
	ans.resize(n);
	tmp.clear();
	for(int i=0; i<n; i++) {
		if(dep[i]%2==0) ans[i] = st[i];
		else ans[i] = ed[i];
		tmp.push_back({ans[i], i});
	}
	sort(tmp.begin(), tmp.end());
	for(int i=0; i<n; i++) {
		ans[tmp[i].second] = i;
	}
	return ans;
}

int find_next_station(int s, int t, std::vector<int> c) {
	if(s == 0) {
		sort(c.begin(), c.end());
		for(int i=0; i<c.size(); i++) if(c[i]>=t) return c[i];
	} else if(c[0] > s) { // s uses start time
		sort(c.begin(), c.end());
		if(t < s || t >= c[c.size()-1]) return c[c.size()-1];
		for(int i=0; i<c.size()-1; i++) if(c[i]>=t) return c[i];
	} else if(c[0] < s) { // s uses end time
		sort(c.begin(), c.end());
		if(t > s || c.size()==1 || t < c[1]) return c[0];
		for(int i=1; i<c.size(); i++) if(i==c.size()-1 || t<c[i+1]) return c[i];
	}
}

Compilation message (stderr)

stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:47:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |   for(int i=0; i<c.size(); i++) if(c[i]>=t) return c[i];
      |                ~^~~~~~~~~
stations.cpp:51:17: 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()-1; i++) if(c[i]>=t) return c[i];
      |                ~^~~~~~~~~~~
stations.cpp:55:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |   for(int i=1; i<c.size(); i++) if(i==c.size()-1 || t<c[i+1]) return c[i];
      |                ~^~~~~~~~~
stations.cpp:55:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |   for(int i=1; i<c.size(); i++) if(i==c.size()-1 || t<c[i+1]) return c[i];
      |                                    ~^~~~~~~~~~~~
stations.cpp:57:1: warning: control reaches end of non-void function [-Wreturn-type]
   57 | }
      | ^

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