Submission #1043373

#TimeUsernameProblemLanguageResultExecution timeMemory
1043373javotazLOSTIKS (INOI20_lostiks)C++17
59 / 100
2043 ms122960 KiB
// In the Name of Allah #include<bits/stdc++.h> using namespace std; #pragma GCC optimize("Ofast,unroll-loops,fast-math") #pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,avx,avx2,sse4.2,popcnt,tune=native") typedef long long ll; #define F first #define S second #define pii pair<int, int> #define pb push_back #define pp pop_back #define all(x) x.begin(), x.end() const int N = 1e6 + 12, M = 20, inf = 2e9 + 7; vector<pii> g[N]; int n, s, t, par[N], dp[(1 << M) + 4][M], p[N], kd[N], bt[M], sz, pd[N], e[N]; pii f[2 * M + 2][2 * M + 2]; bool mrk[N]; vector<int> v, d; void ip() { cin >> n >> s >> t; for (int i = 1; i < n; i++) { int u, v, w; cin >> u >> v >> w; g[u].pb({v, w}); g[v].pb({u, w}); } } void dfs(int u) { for (auto i: g[u]) if (i.F != par[u]) { par[i.F] = u; e[i.F] = e[u] + 1; if (i.S) { pd[i.F] = d.size(), d.pb(i.F), kd[i.F] = i.S; v.pb(u), v.pb(i.S); } dfs(i.F); } } void dfs2(int u, int rt, int h = 0, int mask = 0, int par = -1) { if (mrk[u]) f[rt][p[u]] = {h, mask}; for (auto i: g[u]) if (i.F != par) dfs2(i.F, rt, h + 1, (i.S? (mask | (1 << pd[(e[u] < e[i.F])? i.F : u])) : mask), u); } void solve() { par[s] = s; dfs(s); v.pb(s), v.pb(t); sort(all(v)); v.resize(unique(all(v)) - v.begin()); for (int i = 0; i < v.size(); i++) p[v[i]] = i, mrk[v[i]] = true; for (int i = 0; i < v.size(); i++) dfs2(v[i], i); memset(dp, 127, sizeof dp); int c = d.size(); int ans = inf; for (int mask = 1; mask < (1 << c); ++mask) { sz = 0; for (char i = 0; i < c; i++) if ((mask >> i) & 1) bt[sz++] = i; for (char id1 = 0; id1 < sz; ++id1) { int i = bt[id1]; int u = d[i], ku = kd[d[i]], x = mask ^ (1 << i); if (__builtin_popcount(mask) == 1) { if (f[p[s]][p[ku]].S == x && f[p[ku]][p[par[u]]].S == x) dp[mask][i] = f[p[s]][p[ku]].F + f[p[ku]][p[par[u]]].F; } else if ((f[p[ku]][p[par[u]]].S | x) == x) { for (char id2 = 0; id2 < c; ++id2) if (id1 != id2) { char j = bt[id2]; int v = d[bt[id2]]; if ((f[p[par[v]]][p[ku]].S | x) == x) dp[mask][i] = min(dp[mask][i], dp[x][j] + f[p[par[v]]][p[ku]].F + f[p[ku]][p[par[u]]].F); } } if ((f[p[par[u]]][p[t]].S | mask) == mask) ans = min(ans, dp[mask][i] + f[p[par[u]]][p[t]].F); } } if (f[p[s]][p[t]].S == 0) ans = f[p[s]][p[t]].F; cout << ((ans == inf)? -1 : ans) << '\n'; } int32_t main() { ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); ip(), solve(); return 0; }

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:62:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |  for (int i = 0; i < v.size(); i++)
      |                  ~~^~~~~~~~~~
Main.cpp:64:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |  for (int i = 0; i < v.size(); i++)
      |                  ~~^~~~~~~~~~
Main.cpp:75:15: warning: array subscript has type 'char' [-Wchar-subscripts]
   75 |    int i = bt[id1];
      |               ^~~
Main.cpp:84:19: warning: array subscript has type 'char' [-Wchar-subscripts]
   84 |       char j = bt[id2];
      |                   ^~~
Main.cpp:85:20: warning: array subscript has type 'char' [-Wchar-subscripts]
   85 |       int v = d[bt[id2]];
      |                    ^~~
Main.cpp:87:45: warning: array subscript has type 'char' [-Wchar-subscripts]
   87 |        dp[mask][i] = min(dp[mask][i], dp[x][j] + f[p[par[v]]][p[ku]].F + f[p[ku]][p[par[u]]].F);
      |                                             ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...