Submission #999181

#TimeUsernameProblemLanguageResultExecution timeMemory
999181vjudge1LOSTIKS (INOI20_lostiks)C++17
23 / 100
2079 ms101716 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define inf 0x3F3F3F3F3F3F3F3F struct DSU { vector<int> e; void init(int n) { e.assign(n + 1, -1); } int get(int x) { if (e[x] < 0) return x; return e[x] = get(e[x]); } void unite(int x, int y) { x = get(x), y = get(y); if (x == y) return; if (e[x] > e[y]) swap(x, y); e[x] += e[y]; e[y] = x; } }; const int MXN = 1e6 + 5; const int LOG = 20; int n, S, T, A, B, b = 0; vector<int> adj[MXN]; int p[LOG][MXN], dep[MXN], in[MXN], out[MXN], tim; int id[MXN]; void dfs(int a) { in[a] = ++tim; for (int &v : adj[a]) { if (v == p[0][a]) continue; p[0][v] = a; dep[v] = dep[a] + 1; dfs(v); } out[a] = tim; } vector<array<int, 3>> m; int anc(int u, int v) { return in[u] <= in[v] && out[v] <= out[u]; } int LCA(int u, int v) { if (anc(u, v)) return u; if (anc(v, u)) return v; for (int i = LOG - 1; i >= 0; i--) { if (anc(p[i][u], v)) continue; u = p[i][u]; } return p[0][u]; } int DIST(int u, int v) { return dep[u] + dep[v] - 2 * dep[LCA(u, v)]; } signed main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> S >> T; DSU dsu; dsu.init(n); for (int i = 1; i < n; i++) { int u, v, w; cin >> u >> v >> w; adj[u].push_back(v); adj[v].push_back(u); if (!w) dsu.unite(u, v); else m.push_back({u, v, w}); } p[0][S] = S; dfs(S); for (array<int, 3> &i : m) if (p[0][i[0]] == i[1]) swap(i[0], i[1]); A = dsu.get(S), B = dsu.get(T); int ASD = 0; for (int i = 1; i <= n; i++) { if (dsu.get(i) == i) id[i] = ++ASD; } for (int i = 1; i < LOG; i++) for (int j = 1; j <= n; j++) p[i][j] = p[i - 1][p[i - 1][j]]; vector<int> o(m.size()); iota(o.begin(), o.end(), 0); int res = inf; while (1) { DSU d; d.init(ASD); int f = 1, cur = S, ans = 0; for (int &i : o) { if (d.get(id[A]) == d.get(id[B])) break; if (d.get(id[dsu.get(m[i][0])]) != d.get(id[A]) || d.get(id[dsu.get(m[i][2])]) != d.get(id[A])) { f = 0; break; } d.unite(id[dsu.get(m[i][1])], id[A]); ans += DIST(cur, m[i][2]) + DIST(m[i][2], m[i][0]); cur = m[i][0]; } if (f && d.get(id[A]) == d.get(id[B])) { res = min(res, ans + DIST(cur, T)); } if (!next_permutation(o.begin(), o.end())) break; } cout << (res >= inf ? -1 : res) << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...