Submission #1220824

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220824		brinton	Stations (IOI20_stations)	C++20	0 / 100	307 ms	608 KiB

stations

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

vector<int> label(int N, int k, vector<int> u, vector<int> v) {
	vector<vector<int>> edges(N);
	for(int i = 0;i < u.size();i++){
		edges[u[i]].push_back(v[i]);
		edges[v[i]].push_back(u[i]);
	}
	vector<int> labels(N);
	vector<int> tin(N);
	vector<int> tout(N);

	int gt = 0;
	function<void(int,int,int)> dfs = [&](int cur,int par,int layer){
		tin[cur] = gt++;
		for(auto nxt:edges[cur]){
			if(nxt == par) continue;
			dfs(nxt,cur,1-layer);
		}
		tout[cur] = gt++;
		if(layer == 0) labels[cur] = tin[cur];
		else labels[cur] = tout[cur];
	};

	dfs(0,-1,0);
	return labels;

	
}

int find_next_station(int s, int t, vector<int> c) {
	for(auto &i:c) if(t == i) return i;
	if(c.size() == 1){
		return c[0];
	}else if(s == 0){
		// root, odd layer;
		if(t <= c[0]) return c[0];
		for(int i = 0;i+1 < c.size();i++){
			if(t > c[i] && t <= c[i+1]) return c[i+1];
		}
		
	}else if(s < c[0]){
		// odd layer;
		if(t < s || t > c[c.size()-2]) return c.back();
		if(t > s && t <= c[0]) return c[0];
		for(int i = 0;i+1 < c.size();i++){
			if(t > c[i] && t <= c[i+1]) return c[i+1];
		}
		
	}else{
		// even layer
		if(t > s || t <= c[0]) return c[0];
		if(t < s && t >= c.back()) return c.back();
		for(int i = 1;i+1 < c.size();i++){
			if(t >= c[i] && t < c[i+1]) return c[i];
		}
		assert(false);
	}
	
}

Compilation message (stderr)

stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:62:1: warning: control reaches end of non-void function [-Wreturn-type]
   62 | }
      | ^

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