LGCPC 2024 예선 코드

A. 고장난 계산기
 

#include <bits/stdc++.h>
using namespace std;

int main()
{
	cin.tie(0)->sync_with_stdio(0);
	int n, tmp; cin >> n >> tmp;
	string s; cin >> s;
	vector<int> a(n), b(n);
	for (int i = 0; i < n; i++) if (s[i] == '*') {
		if (s[i - 1] == ')') {
			int t = -1;
			for (int j = i - 2; ; j--) {
				if (s[j] == '(') t++;
				if (s[j] == ')') t--;
				if (!t) { a[j]++; break; }
			}
		}
		else {
			int j = i - 1;
			while (j > 0 && '0' <= s[j - 1] && s[j - 1] <= '9') j--;
			a[j]++;
		}
		if (s[i + 1] == '(') {
			int t = 1;
			for (int j = i + 2; ; j++) {
				if (s[j] == '(') t++;
				if (s[j] == ')') t--;
				if (!t) { b[j]++; break; }
			}
		}
		else {
			int j = i + 1;
			while (j + 1 < n && '0' <= s[j + 1] && s[j + 1] <= '9') j++;
			b[j]++;
		}
	}
	string ans;
	for (int i = 0; i < n; i++) {
		while (a[i]--) ans += '(';
		ans += s[i];
		while (b[i]--) ans += ')';
	}
	cout << ans.size() << '\n' << ans << '\n';
}

 
 
B. 일꾼 고용
 

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int main()
{
	cin.tie(0)->sync_with_stdio(0);
	int tc; cin >> tc;
	while (tc--) {
		int n, k; cin >> n >> k;
		vector<int> c(n + 1), a(n + 1);
		for (int i = 1; i <= n; i++) cin >> c[i];
		for (int i = 1; i <= n; i++) cin >> a[i];
		map<int, ordered_set> mp;
		mp[0].insert(0);
		int t = 0; ll ans = 0, sum = 0;
		for (int i = 1; i <= n; i++) {
			int b = c[i] == 1 ? 1 : -1;
			t += b, sum += b * a[i];
			int cnt = 0;
			if (mp[t].size()) {
				cnt = mp[t].order_of_key(sum + k + 1) - mp[t].order_of_key(sum - k);
			}
			ans += cnt;
			mp[t].insert(sum);
		}
		cout << ans << '\n';
	}
}

 
 
C. 돌고래 사진 (왜 맞는지 모름)
 

#include <bits/stdc++.h>
using namespace std;
const int N = 801;

// ref : anz1217.tistory.com/50

vector<int> ad[N];
int match[N], cache[N];

bool dfs(int u) {
	cache[u] = 1;
	for (int &v : ad[u]) {
		if (cache[match[v]]) continue;
		if (!match[v] || dfs(match[v])) {
			match[v] = u;
			return 1;
		}
	}
	return 0;
}

int main()
{
	cin.tie(0)->sync_with_stdio(0);
	int n, m; cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			int x; cin >> x;
			if (x) ad[j].push_back(i);
		}
	}

	int ans = 0;
	vector<int> v;
	for (int i = m; i >= 2; i--) {
		bool flag = 1;
		for (int j = 0; j < v.size(); j++) {
			if (2 * (ans + 1 - j) > v[j]) flag = 0;
		}
		if (!flag) break;
		memset(cache, 0, sizeof cache);
		if (dfs(i)) ans++, v.push_back(i);
	}
	cout << ans << '\n';
}

 
 
D. 보안 점검 (7점)
 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2001;

int par[N], sz[N]; ll a[N], val[N];

void init(int n) {
	iota(par, par + n + 1, 0);
	fill(sz + 1, sz + n + 1, 1);
	for (int i = 1; i <= n; i++) val[i] = a[i];
}
int fnd(int v) {
	if (par[v] == v) return v;
	return par[v] = fnd(par[v]);
}
void uni(int u, int v) {
	u = fnd(u), v = fnd(v);
	if (u == v) return;
	if (sz[u] < sz[v]) swap(u, v);
	par[v] = u, sz[u] += sz[v], val[u] += val[v];
}

int n, m; ll d;
vector<pair<int, int>> ad[N];

bool solve(int t) {
	init(n);
	for (int u = 1; u <= n; u++) {
		for (auto &[v, w] : ad[u]) {
			if (t >= w) uni(u, v);
		}
	}
	ll mx = 0;
	for (int i = 1; i <= n; i++) {
		if (fnd(i) == i) mx = max(mx, val[i]);
	}
	return mx >= d;
}

int main()
{
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m >> d;
	for (int i = 1; i <= n; i++) cin >> a[i];
	while (m--) {
		int u, v, w; cin >> u >> v >> w;
		ad[u].push_back({v, w});
	}

	int q; cin >> q;
	while (q--) {
		int t; cin >> t;
		if (t == 1) {
			int u, v, w; cin >> u >> v >> w;
			ad[u].push_back({v, w});
		}
		if (t == 2) {
			int k, w; cin >> k >> w;
			a[k] = w;
		}
		if (t == 3) {
			ll D; cin >> D;
			d = D;
		}
		if (t == 4) {
			if (solve(0)) cout << -1 << '\n';
			else if (!solve(600000)) cout << -2 << '\n';
			else {
				int lo = 1, hi = 600000;
				while (lo + 1 < hi) {
					int mi = lo + hi >> 1;
					(solve(mi) ? hi : lo) = mi;
				}
				cout << hi << '\n';
			}
		}
	}
}