Submission #496464

#	Time	Username	Problem	Language	Result	Execution time	Memory
496464		vinnipuh01	Valley (BOI19_valley)	C++17	100 / 100	270 ms	52544 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, mnn[ 100001 ][ 21 ], d[ 100001 ], prr[ 100001 ], b[ 100001 ];
vector <pair<int, int> > v[ 100001 ];
queue <int> vv;
vector <int> v1;
int tmr, tin[ 100001 ], tout[ 100001 ], col[ 100001 ], t[ 400001 ], p[ 400001 ], tt[ 400001 ];
pair <int, int> e[ 100001 ];

void dfs( int u, int pr ) {
	par[ u ][ 0 ] = pr;
	tin[ u ] = ++tmr;
	v1.push_back( u );
	
	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 ];
}

void pus( int v ) {
	if ( p[ v ] ) {
		p[ v + v ] += p[ v ];
		p[ v + v + 1 ] += p[ v ];
		t[ v + v ] += p[ v ];
		t[ v + v + 1 ] += p[ v ];
	}
}

int gett( int a, int b ) {
	mn = oo;
	if ( ok( a, b ) )
		return col[ a ];
	for ( int i = lg; i >= 0; i -- ) {
		if ( !ok( par[ a ][ i ], b )  ) {
			mn = min( mn, mnn[ a ][ i ] );
			a = par[  a][ i ];
		}
	}
	return min( mn, mnn[ a ][ 0 ] );
}


void dfs1( int u, int pr ) {
	mnn[ u ][ 0 ] = min( col[ u ], col[ pr ] );
	for ( int i = 1; i <= lg; i ++ )
		mnn[ u ][ i ] = min( mnn[ u ][ i - 1 ], mnn[ par[ u ][ i - 1 ] ][ i - 1 ]  );
	for ( auto to : v[ u ] ) {
		if ( to.first != pr ) {
			dfs1( to.first, u );
		}
	}
}

void build( int v, int tl, int tr ) {
	if ( tl == tr ) {
		t[ v ] = col[ tl ];
		tt[ v ] = tl;
		return;
	}
	int mid = ( tl + tr ) / 2;
	build(  v + v, tl, mid );
	build( v + v + 1, mid + 1, tr );
	t[ v ] = min( t[ v + v ], t[ v + v + 1 ] );
	if ( t[ v ] == t[ v + v ] )
		tt[ v ] = tt[ v + v ];
	else
		tt[ v ] = tt[ v + v + 1 ];
}

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;
		b[ x ] = 1;
		vv.push( x );
	}
	while ( vv.size() ) {
		if ( col[ par[ vv.front() ][ 0 ] ] > col[ vv.front() ] + prr[ vv.front() ] ) {
			col[ par[ vv.front() ][ 0 ] ] = min( col[ vv.front() ] + prr[ vv.front() ], col[ par[ vv.front() ][ 0 ] ] );
			vv.push( par[ vv.front() ][ 0 ] ); 
		}
		vv.pop();
	}
	for ( int i = 1; i <= n; i ++ ) {
		if ( col[ i ] != oo )
			col[ i ] -= d[ i ];
	}
	dfs1( st, st );
	int l, r, ll, rr;
	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 {
			if ( col[ sum ] == oo ) {
				cout << "oo\n";
			}
			else {
				if ( !b[ r ] ) {
					num = gett( r, sum );
					num += d[ r ];
				}
				else
					num = 0;
				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:135:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  135 | main () {
      | ^~~~
valley.cpp: In function 'int main()':
valley.cpp:167:12: warning: unused variable 'll' [-Wunused-variable]
  167 |  int l, r, ll, rr;
      |            ^~
valley.cpp:167:16: warning: unused variable 'rr' [-Wunused-variable]
  167 |  int l, r, ll, rr;
      |                ^~

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