제출 #496414

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
496414		vinnipuh01	Valley (BOI19_valley)	C++17	23 / 100	232 ms	34528 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 ) {
	mn = col[ a ];
	int pos = -1;
	for ( int i = lg; i >= 0; i -- ) {
		if ( ok( sum, par[ a ][ i ] ) && d[ a ] - d[ par[ a ][ i ] ] + col[ par[ a ][ i ] ] < mn ) {
			mn = d[ a ] - d[ par[ a ][ i ] ] + col[ par[ a ][ i ] ];
			pos = i;
		}
	}
	if ( !pos ) {
		return col[ par[ a ][ 0 ] ] + d[ a ] - d[ par[ a ][ 0 ] ];
	}
	else if ( pos == -1 ) {
		for ( int i = lg; i >= 0; i -- ) {
			if ( ok( sum, par[ a ][ i ] ) && ( d[ a ] - d[ par[ a ][ i ] ] + col[ par[ a ][ i ] ] == mn || mn == oo ) )
				return gett( par[ a ][ i ] ) + d[ a ] - d[ par[ a ][ i ] ];
		}
		return col[ a ];
	}
	return gett( par[ a ][ pos - 1 ] ) + d[ a ] - d[ par[ a ][ pos - 1 ] ];
}
 
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() ) {
		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();
	}
	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 {
			if ( col[ sum ] == oo ) {
				cout << "oo\n";
			}
			else {
				if ( col[ r ] > 0 ) {
					pos = r;
					num = gett( r );
				}
				else
					num = col[ r ];
				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
*/

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

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

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