제출 #1369506

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1369506		gohchingjayk	Shops (NOI24_shops)	C++20	100 / 100	163 ms	39640 KiB

Main

#pragma GCC optimize("O3,inline")
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define int ll

using ii = pair<int, int>;
using iii = pair<int, ii>;

constexpr int MAXN = 500'000 + 5;
constexpr int INF = 1e18 + 5;

ii p[MAXN];
bool duck[MAXN];
bool vis[MAXN];
vector<int> adjlist[MAXN];

void dfs(int x) {
	vis[x] = true;
	for (int ch : adjlist[x]) {
		if (vis[ch]) continue;
		duck[ch] = !duck[x];
		dfs(ch);
	}
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	
	fill(p, p + MAXN, ii{INF, INF});
	
	int N, M; cin >> N >> M;
	for (int i = 0; i < M; ++i) {
		int u, v, w; cin >> u >> v >> w;
		p[u] = min(p[u], ii{w, v});
		p[v] = min(p[v], ii{w, u});
	}
	
	int ans = -INF;
	for (int i = 1; i <= N; ++i) {
		ans = max(ans, p[i].first);
		adjlist[p[i].second].emplace_back(i);
		adjlist[i].emplace_back(p[i].second);
	}
	
	for (int i = 1; i <= N; ++i) {
		if (!vis[i]) dfs(i);
	}
	
	cout << ans << '\n';
	for (int i = 1; i <= N; ++i) cout << (duck[i] ? 'D' : 'B');
}

• 서브태스크 1: 7 / 7
• 서브태스크 2: 13 / 13
• 서브태스크 3: 18 / 18
• 서브태스크 4: 24 / 24
• 서브태스크 5: 38 / 38