Submission #644165

#TimeUsernameProblemLanguageResultExecution timeMemory
644165jumpOverTheWallLOSTIKS (INOI20_lostiks)C++14
59 / 100
2068 ms160768 KiB
#include <bits/stdc++.h> using namespace std; const int N = 1e6; int n, m, s, t, val[N], d[22][N], r[22][N]; int dp[1 << 20][20], key[22], num[22], door[22], distDoor[22], reqDoor[22], dist[22][22], req[22][22]; vector<pair<int, int>> adj[N]; void Dfs(int u, int p, int keyInd) { for(auto e : adj[u]) { int v = e.first; int ind = e.second; if (v == p) continue; r[keyInd][v] = r[keyInd][u] | val[ind]; d[keyInd][v] = d[keyInd][u] + 1; if (keyInd != -1 && val[ind] == (1 << keyInd)) { door[keyInd] = u; distDoor[keyInd] = d[keyInd][u]; reqDoor[keyInd] = r[keyInd][u]; } Dfs(v, u, keyInd); } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> s >> t; s--, t--; for(int i = 0; i < n - 1; i++) { int u, v, w; cin >> u >> v >> w; u--, v--, w--; adj[u].push_back({v, i}); adj[v].push_back({u, i}); if (w >= 0) { key[m] = w; num[m] = i; ++m; } } key[m] = s; key[m + 1] = t; door[m] = s; door[m + 1] = t; for(int i = 0; i < m; i++) val[num[i]] = (1 << i); for(int i = 0; i < m + 2; i++) { Dfs(key[i], -1, i); } for(int i = 0; i < m + 2; i++) for(int j = 0; j < m + 2; j++) { dist[i][j] = d[j][door[i]] + distDoor[j]; req[i][j] = r[j][door[i]] | reqDoor[j]; } int ans = (req[m][m + 1] == 0? dist[m][m + 1] : 1e9); for(int mask = 0; mask < (1 << m); mask++) for(int i = 0; i < m; i++) dp[mask][i] = 1e9; for(int i = 0; i < m; i++) if (req[m][i] == 0) dp[(1 << i)][i] = dist[m][i]; for(int mask = 0; mask < (1 << m); mask++) for(int i = 0; i < m; i++) { if (dp[mask][i] == 1e9) continue; if ((mask & req[i][m + 1]) == req[i][m + 1]) ans = min(ans, dp[mask][i] + dist[i][m + 1]); for(int j = 0; j < m; j++) if ((mask & req[i][j]) == req[i][j]) dp[mask | (1 << j)][j] = min(dp[mask | (1 << j)][j], dp[mask][i] + dist[i][j]); } cout << (ans == 1e9? -1 : ans); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...