Submission #671931

#	Time	Username	Problem	Language	Result	Execution time	Memory
671931		Cutebol	Evacuation plan (IZhO18_plan)	C++17	100 / 100	1712 ms	106144 KiB

plan

#include <bits/stdc++.h>
 
using namespace std;
 
//void fopn(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
#define Scaramouche ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0);
#define int long long
#define itn int
#define endl "\n"
#define ff first
#define ss second
   
const int N = 2e5 + 5 ;
const int mod = 1e9 + 7 ;
const int inf = 1e12 ;

int n , m , k , q , l , tt ;
int p[N] , cost[N] , tin[N] , tout[N] , dep[N] ;
int mn[N][30] ;
bool vis[N] ;
pair <int , int> d[N] ;
vector <int> up[N] ;
vector <int> vec ;
vector <pair <int , int>> g[N] ;
vector <int> gg[N] ;
vector <pair <int , pair <int ,int > > > gr ;

int get( int a ){
	if( p[a] == a ) return a ;
	return p[a] = get(p[a]) ;
}

void un( int a , int b ){
	int aa = get(a) ;
	int bb = get(b) ;
	if ( rand() & 1 ) swap( aa , bb ) ;
	if ( aa != bb ){
		p[aa] = bb ;
		gg[a].push_back(b) ;
		gg[b].push_back(a) ;
	}
}

void djikstra ( int s ){
	d[s] = {0,s} ;
	cost[s] = 0 ;
	set <pair <int , int> > q ;
	q.insert({0,s}) ;
	while ( !q.empty() ){
		int v = q.begin()->second ;
		q.erase(q.begin()) ;
		for ( auto to : g[v] ){
			if ( (d[to.ff].ff) > d[v].ff + to.ss ){
				d[to.ff].ff = d[v].ff + to.ss ;
				d[to.ff].ss = to.ff ;
				cost[to.ff] = d[to.ff].ff ;
				q.insert({d[to.ff].ff,to.ff}) ;
			}
		}
	}
}

void mst(){
	sort ( d , d + n + 1) ;
	reverse( d , d + n + 1 ) ;
	for ( int i = 1 ; i <= n ; i ++ ){
		vis[d[i].ss] = 1 ;
		for ( auto to : g[d[i].ss] ){
			if ( vis[to.ff] ){
				un(d[i].ss,to.ff) ;
			}
		}
	}
}

void dfs( int v , int p = 1 ){
	tin[v] = ++tt ;
	up[v][0] = p ;
	mn[v][0] = cost[v] ;
	dep[v] = dep[p] + 1 ;
	for ( int i = 1 ; i <= l ; i ++ ) up[v][i] = up[up[v][i-1]][i-1] ;
	for ( auto to : gg[v] ){
		if ( to != p ) dfs(to , v ) ;
	}
	tout[v] = ++ tt ;
}

int lca ( int a , int b ){
	if ( dep[a] < dep[b] ) swap(a,b) ;
	int k = dep[a] - dep[b] , ans = inf ;
	for ( int i = 20 ; i >= 0 ; i -- ){
		if ( k & (1<<i) ){
			ans = min ( ans , mn[a][i] ) ;
			a = up[a][i] ;
		}
	}
	if ( a == b ) return min( ans , cost[a] ) ;
	for ( int i = l ; i >= 0 ; i -- ){
		if ( up[a][i] != up[b][i] ){
			ans = min( ans, mn[a][i] ) ;
			ans = min( ans, mn[b][i] ) ;
			a = up[a][i] ;
			b = up[b][i] ;
		}
	}
	ans = min ( {ans , mn[a][1] , mn[b][1] } ) ;
	return ans ;
}
/*
9 12
1 9 4
1 2 5
2 3 7
2 4 3
4 3 6
3 6 4
8 7 10
6 7 5
5 8 1
9 5 7
5 4 12
6 8 2
2
4 7
5
1 6
5 3
4 8
5 8
1 5

*/
void solve(){
	
	cin >> n >> m ;
	while ( 1 << l <= n ) l ++ ;
	for (int i = 0 ; i <= n ; i ++ ){  up[i].resize (l+1) ; }
	for ( int i = 0 ; i <= n ; i ++ ) d[i].ff = inf , p[i] = i ;
	for ( int i = 0 ; i < m ; i ++ ){
		int a , b , w ;
		cin >> a >> b >> w ;
		g[a].push_back({b,w}) ;
		g[b].push_back({a,w}) ;
		gr.push_back({w,{a,b}}) ;
	}
	cin >> k ;
	for ( int i = 0 ; i < k ; i ++ ){
		int x ;
		cin >> x ;
		vec.push_back(x) ;
	}
	for ( auto i : vec ){
		djikstra(i) ;
	}
	mst() ;
//	for ( int i = 1 ; i <= n ; i ++ ){
//		cout << i <<": " ;
//		for ( auto v : gg[i] ) cout << v << " " ;
//		cout <<endl ;
//	}
	for ( int i = 0 ; i <= l ; i ++ )
		for ( int j = 0 ; j <= n ; j ++ ) mn[j][i] = inf ;
	dfs(1) ;
	for ( int i = 1 ; i <= l ; i ++ ){
		for ( int j = 1 ; j <= n ; j ++ ){
			mn[j][i] = min ( mn[j][i-1] , mn[up[j][i-1]][i-1] ) ;
		}
	}
	cin >> q ;
	while ( q -- ){
		int a, b ;
		cin >> a >> b ;
		cout << lca ( a , b ) << endl ;
	}
}
 
signed main(){
//  fopn("talent") ;
//    Scaramouche ;
    int t = 1 ;
//      cin >> t ;
    while ( t -- ) solve() ; 
}

• Subtask 1: 10 / 10
• Subtask 2: 13 / 13
• Subtask 3: 12 / 12
• Subtask 4: 19 / 19
• Subtask 5: 46 / 46