제출 #1096311

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1096311		KickingKun	Valley (BOI19_valley)	C++14	100 / 100	157 ms	36284 KiB

valley

#include <bits/stdc++.h>
 
using namespace std;
 
#define ll long long 
#define ld long double
#define ull unsigned long long
#define bigint __int128
#define pb push_back
#define emb emplace_back
#define pii pair <int, int>
#define fi first
#define se second
#define Task ""
 
#define testBit(n, k) ((n >> k) & 1)
#define flipBit(n, k) (n ^ (1ll << k))
 
template <class T> void minimize(T &a, T b) {if (a > b) a = b;}
template <class T> void maximize(T &a, T b) {if (a < b) a = b;}
 
const int N = 1e5 + 3, LG = 17, mod = 1e9 + 7;
const ll INF = 1e18;

int n, s, q, h;
vector <int> adj[N];
bitset <N> food;

struct Edge {
	int u, v, w;
} e[N];

namespace sub2 {
	ll dist[1005]; ll ans; int del_id;
	void dfs(int u, int p) {
		if (food.test(u)) minimize(ans, dist[u]);
		for (int id: adj[u]) {
			int v = u ^ e[id].u ^ e[id].v, w = e[id].w;
			if (v == p || id == del_id) continue;
			dist[v] = dist[u] + w;
			dfs(v, u);
		}
	}
	
	void solve() {
		while (q--) {
			int r; cin >> del_id >> r;
			memset(dist, -1, sizeof dist);
			dist[r] = 0; ans = INF;
			dfs(r, 0);
			if (dist[h] != -1) cout << "escaped\n";
			else if (ans == INF) cout << "oo\n";
			else cout << ans << '\n';
		}
	}
}

namespace sub4 {
	int dep[N], low[N], tail[N], dfsTimes = 0; // min dis in subtree
	ll opt[N], dist[N];
	void dfs(int u, int p) {
		low[u] = ++dfsTimes;
		if (food.test(u)) opt[u] = 0;
		for (int id: adj[u]) {
			int v = u ^ e[id].u ^ e[id].v, w = e[id].w;
			if (v == p) continue;
			dep[v] = dep[u] + 1;
			dist[v] = dist[u] + w;
			dfs(v, u);
			minimize(opt[u], opt[v] + w);
		}
		tail[u] = dfsTimes;
	}
	
	bool ancestor(int u, int v) { // u is parent of v
		return low[u] <= low[v] && tail[v] <= tail[u];
	}
	
	ll st[N][LG];
	int up[N][LG];
	void calc(int u, int p) {
		for (int id: adj[u]) {
			int v = u ^ e[id].u ^ e[id].v, w = e[id].w;
			if (v == p) continue;
			up[v][0] = u;
			st[v][0] = -dist[u] + opt[u];
			for (int i = 1; i < LG; i++) {
				up[v][i] = up[up[v][i - 1]][i - 1];
				st[v][i] = min(st[v][i - 1], st[up[v][i - 1]][i - 1]);
			}
			calc(v, u);
		}
	}

	void solve() { // dist[r] - dist[p] + opt[p]
		memset(opt, 0x3f, sizeof opt);
		dfs(h, 0); calc(h, 0);
		
		while (q--) {
			int i, r; cin >> i >> r;
			int u = e[i].u, v = e[i].v;
			if (dep[u] > dep[v]) swap(u, v);
			if (!ancestor(v, r)) cout << "escaped\n";
			else {
				ll ans = opt[r]; int cur = r;
				for (int i = 0, k = dep[r] - dep[v]; (1 << i) <= k; i++)
					if (testBit(k, i)) {
						minimize(ans, dist[r] + st[cur][i]);
						cur = up[cur][i];
					}
				if (ans >= INF) cout << "oo\n";
				else cout << ans << '\n';
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
 
	if(fopen(Task".inp", "r")) {
		freopen(Task".inp", "r", stdin);
		freopen(Task".out", "w", stdout);
	}
	
	cin >> n >> s >> q >> h;
	for (int i = 1; i < n; i++) {
		int u, v, w; cin >> u >> v >> w;
		adj[u].emb(i); adj[v].emb(i);
		e[i] = {u, v, w};
	}
	for (int i = 0; i < s; i++) {
		int u; cin >> u; food.set(u);
	}
	
	sub4::solve();
}

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

valley.cpp: In function 'void sub4::calc(int, int)':
valley.cpp:83:35: warning: unused variable 'w' [-Wunused-variable]
   83 |    int v = u ^ e[id].u ^ e[id].v, w = e[id].w;
      |                                   ^
valley.cpp: In function 'int main()':
valley.cpp:122:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |   freopen(Task".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:123:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  123 |   freopen(Task".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 27 / 27
• Subtask 3: 23 / 23
• Subtask 4: 41 / 41