제출 #1178991

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1178991		browntoad	Stations (IOI20_stations)	C++20	21 / 100	304 ms	580 KiB

stations

#include <bits/stdc++.h>
#include "stations.h"
using namespace std;
#define ll long long
// #define int ll
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, n+1)
#define RREP(i, n) for (int i = (n)-1; i >= 0; i--)
#define pii pair<int, int>
// #define f first
//#define s second
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())

static const ll maxn = 1e3+5;
static vector<int> g[maxn];
static vector<int> lab(maxn);

void dfs(int u, int pre, int poo){
	lab[u] = -1;
	for (auto v:g[u]){
		if (v == pre) continue;
		dfs(v, u, poo);
		lab[u] = lab[v]+1;
	}
	if (lab[u] == -1) lab[u] = poo+1;
}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	std::vector<int> labels(n);
	REP(i, n) g[i].clear();

	REP(i, n-1){
		g[u[i]].pb(v[i]);
		g[v[i]].pb(u[i]);
	}

	int spec = -1;
	REP(i, n){
		if (SZ(g[i]) > 2) spec = i;
	}
	if (spec == -1){
		REP(i, n) if (SZ(g[i]) == 1) spec = i;
	}

	REP(i, SZ(g[spec])){
		int toad = i*1000;
		dfs(g[spec][i], spec, toad);
	}
	REP(i, n) labels[i] = lab[i];
	labels[spec] = 0;

	return labels;
}

int find_next_station(int s, int t, std::vector<int> c) {
	if (SZ(c) == 1) return c[0];
	if (s == 0){
		for (auto v:c) if (v/1000 == t/1000) return v;
	}
	int bg = c[0], sm = c.back();
	if (bg < sm) swap(bg, sm);
	if (sm == 0){
		swap(bg, sm);
	}
	if (t == 0){
		return bg;
	}

	if (s/1000 != t/1000){
		return bg;
	}
	if (s > t){
		return sm;
	}
	else return bg;
}

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