제출 #1050146

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1050146		idas	기지국 (IOI20_stations)	C++17	100 / 100	523 ms	1048 KiB

stations

#include "stations.h"
#include "bits/stdc++.h"
#define FOR(i, begin, end) for(int i=(begin); i<(end); i++)
#define sz(x) ((int)((x).size()))
#define pb push_back

using namespace std;
typedef vector<int> vi;

const int N=1e3+10;
int in[N], dp[N], id;
vi ad[N];

void dfs(int u, int pst=-1) {
	if(dp[u]&1^1) in[u]=id++;
	for(auto it : ad[u]) {
		if(it==pst) continue;
		dp[it]=dp[u]+1;
		dfs(it, u);
	}
	if(dp[u]&1) in[u]=id++;
}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	FOR(i, 0, n) ad[i].clear(), dp[i]=in[i]=0;
	FOR(i, 0, n-1) {
		ad[u[i]].pb(v[i]), ad[v[i]].pb(u[i]);
	}
	id=0; dfs(0);
	vi b(n); FOR(i, 0, n) b[i]=in[i];
	return b;
}

int find_next_station(int s, int t, std::vector<int> c) {
	if(s<c[0]) {
		if(t<s) return c[sz(c)-1];
		FOR(i, 0, sz(c)) {
			if(t<=c[i]) return c[i];
		}
		return c[sz(c)-1];
	}
	else {
		if(t>s) return c[0];
		for(int i=sz(c)-1; i>=0; i--) {
			if(t>=c[i]) return c[i];
		}
		return c[0];
	}
}
/*
2
5 10
0 1
1 2
1 3
2 4
2
2 0 1
1 3 3
5 10
0 1
1 2
2 3
3 4
1
4 0 2
*/

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

stations.cpp: In function 'void dfs(int, int)':
stations.cpp:15:10: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   15 |  if(dp[u]&1^1) in[u]=id++;
      |     ~~~~~^~

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