Submission #496298

#	Time	Username	Problem	Language	Result	Execution time	Memory
496298		vinnipuh01	Valley (BOI19_valley)	C++17	36 / 100	3056 ms	32200 KiB

valley

#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <stack>
#include <string>
#include <map>
#include <queue>
#define int long long

using namespace std;

const long long oo = 1000000000000000000;

long long  sum, ans = 0, mx = 0, mn = 1000000000, num, pos;


/*
    ViHHiPuh

   (( `'-""``""-'` ))
     )-__-_.._-__-(
   / --- (o _ o) --- \
   \ .-* ( .0. ) *-. /
   _'-. ,_ '=' _, .-'_
  / `;#'#'# - #'#'#;` \
 \_)) -----'#'----- ((_/
      # --------- #
  '# ------- ------ #'
  /..-'# ------- #'-.\
  _\...-\'# -- #'/-.../_
  ((____)- '#' -(____))


    cout << fixed << setprecision(6) << x;


    freopen ( "sum.in", "r", stdin )
*/

int n, m, q, st, par[ 100001 ][ 21 ], lg = 20, d[ 100001 ], prr[ 100001 ];
vector <pair<int, int> > v[ 100001 ];
queue <int> vv;
int tmr, tin[ 100001 ], tout[ 100001 ], col[ 100001 ];
pair <int, int> e[ 100001 ];

void dfs( int u, int pr ) {
	par[ u ][ 0 ] = pr;
	tin[ u ] = ++tmr;
	for ( int i = 1; i <= lg; i ++ )
		par[ u ][ i ] = par[ par[ u ][ i  - 1 ] ][ i - 1 ];
	for ( auto to : v[ u ] ) {
		if ( to.first != pr ) {
			prr[ to.first ] = to.second;
			d[ to.first ] = d[ u ] + to.second;
			dfs( to.first, u );
		}
	}
	tout[ u ] = tmr;
}

bool ok( int a, int b ) {
	return ( tin[  a] <= tin[ b ] && tout[ a ] >= tout[ b ] );
}

int lca( int a, int b ) {
	if ( ok( a, b ) )
		return a;
	if ( ok( b, a ) )
		return b;
	for ( int i = lg; i >= 0; i -- ) {
		if ( !ok( par[ a ][ i ], b ) )
			a = par[ a ][ i ];
	}
	return par[ a ][ 0 ];
}

int gett( int a, int b ) {
	mn = oo;
	while ( !ok( a, b ) ) {
		mn = min( mn, col[ a ] + d[ pos ] - d[ a ] + 0ll );
		a = par[ a ][ 0 ];
	}
	mn = min( mn, col[ a ] + d[ pos ] - d[ a ] + 0ll );
	return mn;
}

void dfs1( int u, int pr ) {
	for ( auto to : v[ u ] ) {
		if ( to.first != pr ) {
			if ( col[ to.first ] > col[ u ] + to.second ) {
				col[ to.first ] = col[ u ] + to.second;
				vv.push( to.first );
			}
			dfs1( to.first, u );
		}
	}
}

main () {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
	cin >> n >> m >> q >> st;
	int x, y, z;
	for ( int i = 1; i < n; i ++ ) {
		cin >> x >> y >> z;
		v[ x ].push_back( { y, z } );
		v[ y ].push_back( { x, z } );
		e[ i ] = { x, y };
	}
	for ( int i = 1; i <= n; i ++ )
		col[ i ] = oo;
	dfs( st, st );
	for ( int i = 1; i <= m; i ++ ) {
		cin >> x;
		col[ x ] = 0;
		vv.push( x );
	}
	while ( vv.size() ) {
		col[ par[ vv.front() ][ 0 ] ] = min( col[ vv.front() ] + prr[ vv.front() ], col[ par[ vv.front() ][ 0 ] ] );
		if ( vv.front() == par[ vv.front() ][ 0 ] ) {
			vv.pop();
			continue;
		}
		vv.push( par[ vv.front() ][ 0 ] );
		vv.pop();
	}
	int l, r;
	while ( q -- ) {
		cin >> l >> r;
//		cout << l << " " << r << "     ";
		sum = ans = num = 0;
		if ( d[ e[ l ].first ] < d[ e[ l ].second ] ) {
			num = e[ l ].first;
			sum = e[ l ].second;
		}
		else {
			num = e[ l ].second;
			sum = e[ l ].first;
		}
		ans = lca( r, sum );
//		cout << ans << " " << sum << " - ";
		if ( ans != sum ) {
			cout << "escaped\n";
		}
		else {
			mn = 1e9;
			if ( col[ sum ] == oo ) {
				cout << "oo\n";
			}
			else {
				if ( col[ sum ] != col[ r ] ) {
					pos = r;
					num = gett( r, sum );
				}
				else
					num = col[ sum ];
				cout << num << "\n";
			}
		}
	}
}

/*
8 8 10 2
1 2 1
2 3 1
3 4 1
2 5 1
5 8 1
3 6 1
7 4 1
1 2 3 4 5 6 7 8
2 7
1 1
4 8
2 6
6 6
3 3
7 6
2 2
5 5
1 1
1 1
1 1
1 1
1 1
*/

Compilation message (stderr)

valley.cpp:103:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  103 | main () {
      | ^~~~

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