제출 #833710

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
833710		penguinman	기지국 (IOI20_stations)	C++17	0 / 100	587 ms	564 KiB

stations

#include "stations.h"
#include <bits/stdc++.h>

#ifndef EVAL
#include "stub.cpp"
#endif

using ll = int;
using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::string;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;

#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define ln "\n"
#define pb emplace_back
#define mp std::make_pair
#define mtp std::make_tuple
#define all(a) a.begin(), a.end()

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	constexpr int max = 2000;
	int ord = 0;
	vi left(n, -1), right(n, -1);
	vii edge(n);
	rep(i,0,n-1){
		edge[u[i]].pb(v[i]);
		edge[v[i]].pb(u[i]);
	}
	vector<bool> flag(n);
	std::function<void(int)> dfs = [&](int now){
		left[now] = ord++;
		for(auto next: edge[now]){
			if(left[next] == -1){
				flag[next] = !flag[now];
				dfs(next);
			}
		}
		right[now] = ord-1;
	};
	dfs(0);
	vi num(n);
	rep(i,0,n){
		if(flag[i]) num[i] = left[i]*2;
		else num[i] = right[i]*2+1;
	}
	num[0] = max;
	return num;
}

int find_next_station(int s, int t, std::vector<int> c) {
	constexpr int max = 2000;
	int lt = t/2, rt = t/2;
	int ls, rs;
	sort(all(c));
	// right
	if(s%2){
		rs = s/2;
		if(s == max){
			rs = max;
			ls = 0;
		}
		else{
			if(c.size() == 1) ls = rs;
			else ls = c[1];
		}

		if(ls <= lt && rt <= rs){
			int start = 1;
			if(s == max) start = 0;
			c.pb((rs+1)*2);
			rep(i,start,c.size()){
				int el = c[i];
				int lc = el/2, rc = c[i+1]/2-1;
				if(lc <= lt && rt <= rc) return el;
			}
		}
		else{
			return c[0];
		}
	}
	// left
	else{
		ls = s/2;
		if(c.size() == 1) rs = ls;
		else rs = c[c.size()-2];

		reverse(all(c));
		if(ls <= lt && rt <= rs){
			int start = 1;
			c.pb(ls*2);
			rep(i,start,c.size()){
				int el = c[i];
				int lc = c[i+1]/2+1, rc = el/2;
				if(lc <= ls && rs <= rc) continue;
				if(lc <= lt && rt <= rc) return el;
			}
		}
		else{
			return c[0];
		}
	}
	
}

컴파일 시 표준 에러 (stderr) 메시지

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

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