Submission #635323

#	Time	Username	Problem	Language	Result	Execution time	Memory
635323		S2speed	LOSTIKS (INOI20_lostiks)	C++17	59 / 100	2098 ms	399020 KiB

Main

#include<bits/stdc++.h>

using namespace std;

#pragma GCC optimize ("Ofast")

#define sze(x) (ll)(x.size())
typedef long long ll;
typedef pair<ll , ll> pll;

const ll maxn = (1 << 20) + 17 , inf = 2e16;

ll n , s , t;
vector<pll> adj[maxn];
vector<ll> dis[maxn] , bfs;
ll g[maxn] , k[22] , d[22] , e[22] , dp[maxn][22];

void BFS(ll r , bool f = false){
	bfs.clear();
	dis[r].assign(n , inf);
	dis[r][r] = 0;
	g[r] = 0;
	bfs.push_back(r);
	ll x = 0;
	while(x < sze(bfs)){
		ll v = bfs[x++];
		for(auto p : adj[v]){
			ll i = p.first , t = p.second;
			if(dis[r][i] < dis[r][v] + 1) continue;
			if(f){
				g[i] = g[v];
				if(t != -1){
					g[i] ^= (1 << t);
					d[t] = v;
				}
			}
			dis[r][i] = dis[r][v] + 1;
			bfs.push_back(i);
		}
	}
	return;
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	memset(dp , 63 , sizeof(dp));
	cin>>n>>s>>t; s--; t--;
	ll m = 0;
	for(ll i = 1 ; i < n ; i++){
		ll v , u , w;
		cin>>v>>u>>w; v--; u--; w--;
		if(w != -1){
			k[m] = w;
			adj[v].push_back({u , m}); adj[u].push_back({v , m});
			m++;
		} else {
			adj[v].push_back({u , w}); adj[u].push_back({v , w});
		}
	}
	BFS(s , true);
	if(g[t] == 0){
		cout<<dis[s][t]<<'\n';
		return 0;
	}
	for(ll j = 0 ; j < m ; j++){
		e[j] = g[k[j]] | g[d[j]];
		BFS(d[j]);
		if(e[j] == 0){
			dp[(1 << j)][j] = dis[s][k[j]] + dis[d[j]][k[j]];
		}
	}
	ll lm = (1 << m);
	for(ll mask = 1 ; mask < lm ; mask++){
		for(ll j = 0 ; j < m ; j++){
			if(mask & (1 << j)) continue;
			if((e[j] & mask) != e[j]) continue;
			ll h = inf;
			for(ll i = 0 ; i < m ; i++){
				if(!(mask & (1 << i))) continue;
				h = min(h , dp[mask][i] + dis[d[i]][k[j]] + dis[d[j]][k[j]]);
			}
			dp[mask ^ (1 << j)][j] = min(dp[mask ^ (1 << j)][j] , h);
		}
	}
//	cout<<dp[2][1]<<' '<<dp[6][2]<<' '<<dp[7][0]<<'\n';
//	cout<<dis[d[0]][t]<<'\n';
	ll ans = inf;
	for(ll mask = 1 ; mask < lm ; mask++){
		if((g[t] & mask) != g[t]) continue;
		ll h = inf;
		for(ll i = 0 ; i < m ; i++){
			if(!(mask & (1 << i))) continue;
//			cout<<mask<<' '<<i<<'\n';
			h = min(h , dp[mask][i] + dis[d[i]][t]);
		}
		ans = min(ans , h);
	}
	cout<<(ans == inf ? -1 : ans)<<'\n';
	return 0;
}

• Subtask 1: 23 / 23
• Subtask 2: 36 / 36
• Subtask 3: 0 / 41