Submission #1101704

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101704		hungeazy	Valley (BOI19_valley)	C++17	100 / 100	137 ms	73800 KiB

valley

/*
* @Author: hungeazy
* @Date:   2024-10-16 08:23:59
* @Last Modified by:   hungeazy
* @Last Modified time: 2024-10-16 13:32:20
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
// #pragma GCC optimize("O3")  
// #pragma GCC optimize("unroll-loops")  
// #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")  
using namespace std;
using namespace __gnu_pbds; 
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define int long long
#define ll long long 
#define ull unsigned long long
#define sz(x) x.size()
#define sqr(x) (1LL * (x) * (x))
#define all(x) x.begin(), x.end()
#define fill(f,x) memset(f,x,sizeof(f))
#define FOR(i,l,r) for(int i=l;i<=r;i++)
#define FOD(i,r,l) for(int i=r;i>=l;i--)
#define debug(x) cout << #x << " = " << x << '\n'
#define ii pair<int,int>
#define iii pair<int,ii>
#define di pair<ii,ii>
#define vi vector<int>
#define vii vector<ii>
#define mii map<int,int>
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define fi first
#define se second
#define pb push_back
#define MOD 1000000007
#define __lcm(a,b) (1ll * ((a) / __gcd((a), (b))) * (b))
#define YES cout << "YES\n"
#define NO cout << "NO\n"
#define MASK(i) (1LL << (i))
#define c_bit(i) __builtin_popcountll(i)
#define BIT(x,i) ((x) & MASK(i))
#define SET_ON(x,i) ((x) | MASK(i))
#define SET_OFF(x,i) ((x) & ~MASK(i))
#define oo 1e18
#define name "LANDSLIDE"
#define endl '\n'
#define time() cerr << endl << "-------------Time:" << 1000.0 * clock() / CLOCKS_PER_SEC << "ms.";
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
const int N = (int)1e5+10;
int n,S,Q,H,a[N];
iii edge[N];

namespace sub12 {

	vii g[N];
	int d[N];

	bool approved()
	{
		return n <= 1e3 and Q <= 1e3;
	}

	void BFS(int p)
	{
		FOR(i,1,n) d[i] = oo;
		d[p] = 0;
		priority_queue<ii,vii,greater<ii>> q;
		q.push({0,p});
		while (!q.empty())
		{
			int u = q.top().se, cost = q.top().fi;
			q.pop();
			if (cost > d[u]) continue;
			for (ii x : g[u])
			{
				int v,w;
				tie(v,w) = x;
				if (d[v] > d[u]+w)
				{
					d[v] = d[u]+w;
					q.push({d[v],v});
				}
			}
		}
	}

	void solve(void)
	{
		while (Q--)
		{
			int I,R;
			cin >> I >> R;
			FOR(i,1,n) g[i].clear();
			FOR(i,1,n-1)
				if (i != I)
				{
					int u = edge[i].fi, v = edge[i].se.fi, w = edge[i].se.se;
					g[u].pb({v,w}); g[v].pb({u,w});
				}
			BFS(R);
			if (d[H] != oo) cout << "escaped" << endl;
			else  
			{
				int ans = oo;
				FOR(i,1,S) minimize(ans,d[a[i]]);
				if (ans == oo) cout << "oo" << endl;
				else cout << ans << endl;
			}
		}
	}
	
}

namespace sub345 {

	int h[N],in[N],out[N],cnt=0,dem[N];
	bool check[N];
	vii g[N];

	struct Node {

		int len,mn,par;

	} f[N][20];

	void DFS(int u, int p)
	{
		in[u] = ++cnt;
		if (check[u]) dem[u] = 1;
		else f[u][0].mn = oo;
		for (ii x : g[u])
		{
			int v,w;
			tie(v,w) = x;
			if (v == p) continue;
			h[v] = h[u]+1;
			f[v][0].par = u;
			f[v][0].len = w;
			DFS(v,u);
			dem[u] += dem[v];
			minimize(f[u][0].mn,f[v][0].mn+w);
		}
		out[u] = cnt;
	}

	void init()
	{
		FOR(j,1,log2(n))
			FOR(i,1,n)
			{
				f[i][j].par = f[f[i][j-1].par][j-1].par;
				f[i][j].len = f[i][j-1].len+f[f[i][j-1].par][j-1].len;
				f[i][j].mn = min(f[i][j-1].mn,f[f[i][j-1].par][j-1].mn+f[i][j-1].len);
			}
	}

	void solve(void)
	{
		FOR(i,1,n-1)
		{
			int u = edge[i].fi, v = edge[i].se.fi, w = edge[i].se.se;
			g[u].pb({v,w}); g[v].pb({u,w});
		}		
		FOR(i,1,S) check[a[i]] = true;
		DFS(H,-1);
		init();
		// FOR(i,1,n) cout << in[i] << " " << out[i] << endl;
		while (Q--)
		{
			int I,R;
			cin >> I >> R;
			int u = edge[I].fi, v = edge[I].se.fi;
			if (h[u] > h[v]) swap(u,v);
			if (in[R] >= in[v] and in[R] <= out[v])
			{
				if (!dem[v]) cout << "oo" << endl;
				else 
				{
					int len = 0, ans = oo;
					FOD(i,log2(n),0)
						if (h[f[R][i].par] >= h[v])
						{
							minimize(ans,f[R][i].mn+len);
							len += f[R][i].len;
							R = f[R][i].par;
						}
					cout << min(ans,f[R][0].mn+len) << endl;
				}
			}
			else cout << "escaped" << endl;
		}
	}

}

signed main()
{
    fast;
    if (fopen(name".inp","r"))
    {
    	freopen(name".inp","r",stdin);
    	freopen(name".out","w",stdout);
    }
    cin >> n >> S >> Q >> H;
    FOR(i,1,n-1)
   	{
   		int u,v,w;
   		cin >> u >> v >> w;
   		edge[i] = {u,{v,w}};
   	}
   	FOR(i,1,S) cin >> a[i];
   	// if (sub12::approved()) sub12::solve();
   	// else 
   	sub345::solve();
    time();
    return 0;
}
// ██░ ██  █    ██  ███▄    █   ▄████
//▓██░ ██▒ ██  ▓██▒ ██ ▀█   █  ██▒ ▀█▒
//▒██▀▀██░▓██  ▒██░▓██  ▀█ ██▒▒██░▄▄▄░
//░▓█ ░██ ▓▓█  ░██░▓██▒  ▐▌██▒░▓█  ██▓
//░▓█▒░██▓▒▒█████▓ ▒██░   ▓██░░▒▓███▀▒
// ▒ ░░▒░▒░▒▓▒ ▒ ▒ ░ ▒░   ▒ ▒  ░▒   ▒
// ▒ ░▒░ ░░░▒░ ░ ░ ░ ░░   ░ ▒░  ░   ░
// ░  ░░ ░ ░░░ ░ ░    ░   ░ ░ ░ ░   ░
// ░  ░  ░   ░              ░       ░

Compilation message (stderr)

valley.cpp: In function 'int main()':
valley.cpp:203:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  203 |      freopen(name".inp","r",stdin);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
valley.cpp:204:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  204 |      freopen(name".out","w",stdout);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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