제출 #833916

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
833916		penguinman	기지국 (IOI20_stations)	C++17	100 / 100	798 ms	804 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) {
	if(k == 1000){
		vi num(n);
		rep(i,0,n) num[i] = i;
	}
	constexpr int max = 1000;
	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){
		if(flag[now]) left[now] = ord++;
		else left[now] = -2;
		for(auto next: edge[now]){
			if(left[next] == -1){
				flag[next] = !flag[now];
				dfs(next);
			}
		}
		if(!flag[now]) right[now] = ord++;
	};
	dfs(0);
	vi num(n);
	rep(i,0,n){
		if(flag[i]) num[i] = left[i];
		else num[i] = right[i];
	}
	num[0] = max;
	return num;
}

int find_next_station(int s, int t, std::vector<int> c) {
	constexpr int max = 1000;
	sort(all(c));
	int ls, rs;
	// left
	if(c[0] > s){
		ls = s;
		reverse(all(c));
		if(c.size() == 1) rs = ls;
		else rs = c[1];

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

		if(ls <= t && t <= rs){
			int start = 1;
			if(s == max) start = 0;
			c.pb(rs+1);
			rep(i,start,c.size()-1){
				int el = c[i];
				int lc = el, rc = c[i+1]-1;
				if(lc <= t && t <= rc) return el;
			}
		}
		else{
			return c[0];
		}
	}
	else assert(false);
	
}

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

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

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