oj.uz

답안 #496269

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
496269 2021-12-21T04:27:32 Z vinnipuh01 Valley (BOI19_valley) C++17
0 / 100
 131 ms 18588 KB 
#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <stack>
#include <string>
#include <map>
#include <queue>

using namespace std;

const long long oo = 1000000000000000000;

long long int  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 = 1 ) {
	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 );
		}
	}
}

int 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 ] = mn;
	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 ] )
			break;
		vv.push( par[ vv.front() ][ 0 ] );
		vv.pop();
	}
	int l, r;
	while ( q -- ) {
		cin >> l >> r;
		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 );
		if ( ans != sum ) {
			cout << "escaped\n";
		}
		else {
			mn = 1e9;
			if ( col[ sum ] == mn ) {
				cout << "oo\n";
			}
			else {
				pos = r;
				num = gett( r, sum );
				cout << 0 << "\n";
			}
		}
	}
}

/*
5 2 3 1
1 2 3
1 3 2
3 4 1
3 5 2
2
4
2 2
2 5
4 5
*/

Subtask #1
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 2764 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 2764 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 131 ms 18588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 2764 KB Output isn't correct
2 Halted 0 ms 0 KB -