oj.uz

Submission #633696

# Submission time Handle Problem Language Result Execution time Memory
633696 2022-08-23T05:29:12 Z NothingXD LOSTIKS (INOI20_lostiks) C++17
0 / 100
 192 ms 62160 KB 
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
//typedef __uint128_t L;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
	cerr << " " << H;
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
#define F first
#define S second

const int maxn = 1e6 + 10;
const int maxm = 20;
const int mask = (1 << 20);
const int inf = 1e9;

int n, m, S, T, edge[maxm][3], comp[maxn], cnt, sz, par[mask][maxm+1], h[2*maxm+4][maxn], dp[mask][2*maxm+4];
vector<int> t[maxn], g[maxn], G[maxm+1];
vector<pii> ver;
bool vis[maxn];
void dfs(int v, int *h, int p = -1){
	for (auto u: t[v]){
		if (u != p){
			h[u] = h[v] + 1;
			dfs(u, h, v);
		}
	}
}

void getcomp(int v, int p = -1){
	vis[v] = true;
	comp[v] = cnt;
	for (auto u: g[v]) if (u != p) getcomp(u, v);
}

void getpar(int v, int *par, int p = -1){
	vis[v] = true;
	par[v] = sz;
	for (auto u : G[v]) if (u != p) getpar(u, par, v);
}

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

	cin >> n >> S >> T;
	ver.push_back({S, -1});
	ver.push_back({T, -1});
	for (int i = 1; i < n; i++){
		int u, v, w; cin >> u >> v >> w;
		t[u].push_back(v);
		t[v].push_back(u);
		if (w == 0){
			g[u].push_back(v);
			g[v].push_back(u);
		}
		else{
			edge[m][0] = u;
			edge[m][1] = v;
			edge[m][2] = w;
			ver.push_back({u, m});
			ver.push_back({v, m});
			m++;
		}
	}

	sort(all(ver));
	ver.resize(distance(ver.begin(), unique(all(ver))));

	for (int i = 1; i <= n; i++){
		if (!vis[i]){
			getcomp(i);
			cnt++;
		}
	}

	for (int i = 0; i < (1 << m); i++){
		for (int j = 0; j < m+1; j++){
			G[j].clear();
			vis[j] = false;
		}
		for (int j = 0; j < m; j++){
			if (!((i >> j) & 1)){
				G[comp[edge[j][0]]].push_back(comp[edge[j][1]]);
				G[comp[edge[j][1]]].push_back(comp[edge[j][0]]);
			}
		}
		sz = 0;
		for (int j = 0; j < m+1; j++){
			if (!vis[j]){
				sz++;
				getpar(j, par[i]);
			}
		}
	}

	int vers = ver.size();

	for (int i = 0; i < vers; i++){
		dfs(ver[i].F, h[i]);
	}

	for (int i = 0; i < vers; i++){
		dp[0][i] = h[i][T];
	}

	for (int msk = 1; msk < (1 << m); msk++){
		for (int i = 0; i < vers; i++){
			int v = ver[i].F;
			dp[msk][i] = inf;
			if (ver[i].F == T){
				dp[msk][i] = 0;
				continue;
			}
			for (int j = 0; j < vers; j++){
				if (ver[j].S == -1 && ver[i].F == T && par[msk][comp[T]] == par[msk][comp[v]]){
					dp[msk][i] = min(dp[msk][i], h[i][T]);
				}
				else if (ver[j].S != -1 && ((msk >> ver[j].S) & 1) && par[msk][comp[ver[j].F]] == par[msk][comp[v]]){
					dp[msk][i] = min(dp[msk][i], dp[msk^(1 << ver[j].S)][j] + h[i][edge[ver[j].S][2]] + h[j][edge[ver[j].S][2]]);
				}
			}
		}
	}

	for (int i = 0; i < vers; i++){
		if (ver[i].F == S) return cout << dp[(1 << m) - 1][i] << '\n', 0;
	}



	return 0;
}

Subtask #1
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47316 KB Output is correct
2 Correct 24 ms 47284 KB Output is correct
3 Incorrect 192 ms 62160 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47276 KB Output is correct
2 Correct 24 ms 47244 KB Output is correct
3 Incorrect 25 ms 47748 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47316 KB Output is correct
2 Correct 24 ms 47284 KB Output is correct
3 Incorrect 192 ms 62160 KB Output isn't correct
4 Halted 0 ms 0 KB -