| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1043625 |
2024-08-04T12:22:36 Z |
javotaz |
LOSTIKS (INOI20_lostiks) |
C++17 |
|
15 ms |
118108 KB |
// 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 = 1e9 + 7;
vector<pii> g[N];
int n, s, t, par[N], dp[(1 << M) + 4][M], p[N], kd[N], pd[N], e[N], dis[2 * M + 2][2 * M + 2];
pii f[2 * M + 2][2 * M + 2];
bool mrk[N];
char l[N], r[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}, dis[rt][p[u]] = h;
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, 63, sizeof dp);
}
bool check(int v, int u, int x) {
return ((f[l[v]][r[u]].S | x) == x) && ((f[r[u]][l[u]].S | x) == x);
}
int32_t main() {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
ip(), solve();
int c = d.size();
int ans = inf;
for (int i = 0; i < c; i++)
l[i] = p[par[d[i]]], r[i] = p[kd[d[i]]];
for (int mask = 1; mask < (1 << c); ++mask)
for (int i = 0; i < c; ++i)
if ((mask >> i) & 1) {
int x = (mask ^ (1 << i));
if (!x) {
if ((f[p[s]][r[i]].S | x) == x && (f[r[i]][l[i]].S | x) == x)
dp[mask][i] = f[p[s]][r[i]].F + f[r[i]][l[i]].F;
}
else {
int u = __builtin_ctz(x), y = inf;
auto &s = dis[r[i]];
int z = x;
char j;
for (; z; z ^= z & -z)
y = ((y < s[l[j = __builtin_ctz(z)]] + dp[x][j])? y : s[l[j]] + dp[x][j]);
dp[mask][i] = y + s[l[i]];
}
if ((f[l[i]][p[t]].S | mask) == mask)
ans = min(ans, dp[mask][i] + f[l[i]][p[t]].F);
}
if (f[p[s]][p[t]].S == 0)
ans = f[p[s]][p[t]].F;
cout << ((ans >= inf)? -1 : ans) << '\n';
return 0;
}
Compilation message
Main.cpp: In function 'void solve()':
Main.cpp:63:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | for (int i = 0; i < v.size(); i++)
| ~~^~~~~~~~~~
Main.cpp:65:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | for (int i = 0; i < v.size(); i++)
| ~~^~~~~~~~~~
Main.cpp: In function 'bool check(int, int, int)':
Main.cpp:71:16: warning: array subscript has type 'char' [-Wchar-subscripts]
71 | return ((f[l[v]][r[u]].S | x) == x) && ((f[r[u]][l[u]].S | x) == x);
| ~~~^
Main.cpp:71:22: warning: array subscript has type 'char' [-Wchar-subscripts]
71 | return ((f[l[v]][r[u]].S | x) == x) && ((f[r[u]][l[u]].S | x) == x);
| ~~~^
Main.cpp:71:48: warning: array subscript has type 'char' [-Wchar-subscripts]
71 | return ((f[l[v]][r[u]].S | x) == x) && ((f[r[u]][l[u]].S | x) == x);
| ~~~^
Main.cpp:71:54: warning: array subscript has type 'char' [-Wchar-subscripts]
71 | return ((f[l[v]][r[u]].S | x) == x) && ((f[r[u]][l[u]].S | x) == x);
| ~~~^
Main.cpp: In function 'int32_t main()':
Main.cpp:86:22: warning: array subscript has type 'char' [-Wchar-subscripts]
86 | if ((f[p[s]][r[i]].S | x) == x && (f[r[i]][l[i]].S | x) == x)
| ~~~^
Main.cpp:86:46: warning: array subscript has type 'char' [-Wchar-subscripts]
86 | if ((f[p[s]][r[i]].S | x) == x && (f[r[i]][l[i]].S | x) == x)
| ~~~^
Main.cpp:86:52: warning: array subscript has type 'char' [-Wchar-subscripts]
86 | if ((f[p[s]][r[i]].S | x) == x && (f[r[i]][l[i]].S | x) == x)
| ~~~^
Main.cpp:87:32: warning: array subscript has type 'char' [-Wchar-subscripts]
87 | dp[mask][i] = f[p[s]][r[i]].F + f[r[i]][l[i]].F;
| ~~~^
Main.cpp:87:44: warning: array subscript has type 'char' [-Wchar-subscripts]
87 | dp[mask][i] = f[p[s]][r[i]].F + f[r[i]][l[i]].F;
| ~~~^
Main.cpp:87:50: warning: array subscript has type 'char' [-Wchar-subscripts]
87 | dp[mask][i] = f[p[s]][r[i]].F + f[r[i]][l[i]].F;
| ~~~^
Main.cpp:91:23: warning: array subscript has type 'char' [-Wchar-subscripts]
91 | auto &s = dis[r[i]];
| ~~~^
Main.cpp:95:23: warning: array subscript has type 'char' [-Wchar-subscripts]
95 | y = ((y < s[l[j = __builtin_ctz(z)]] + dp[x][j])? y : s[l[j]] + dp[x][j]);
| ~~^~~~~~~~~~~~~~~~~~
Main.cpp:95:41: warning: array subscript has type 'char' [-Wchar-subscripts]
95 | y = ((y < s[l[j = __builtin_ctz(z)]] + dp[x][j])? y : s[l[j]] + dp[x][j]);
| ~~~~~~~~~~~~~~~~~~~~~~^
Main.cpp:95:52: warning: array subscript has type 'char' [-Wchar-subscripts]
95 | y = ((y < s[l[j = __builtin_ctz(z)]] + dp[x][j])? y : s[l[j]] + dp[x][j]);
| ^
Main.cpp:95:65: warning: array subscript has type 'char' [-Wchar-subscripts]
95 | y = ((y < s[l[j = __builtin_ctz(z)]] + dp[x][j])? y : s[l[j]] + dp[x][j]);
| ^
Main.cpp:95:66: warning: array subscript has type 'char' [-Wchar-subscripts]
95 | y = ((y < s[l[j = __builtin_ctz(z)]] + dp[x][j])? y : s[l[j]] + dp[x][j]);
| ~~~^
Main.cpp:95:77: warning: array subscript has type 'char' [-Wchar-subscripts]
95 | y = ((y < s[l[j = __builtin_ctz(z)]] + dp[x][j])? y : s[l[j]] + dp[x][j]);
| ^
Main.cpp:95:23: warning: operation on 'j' may be undefined [-Wsequence-point]
95 | y = ((y < s[l[j = __builtin_ctz(z)]] + dp[x][j])? y : s[l[j]] + dp[x][j]);
| ~~^~~~~~~~~~~~~~~~~~
Main.cpp:96:29: warning: array subscript has type 'char' [-Wchar-subscripts]
96 | dp[mask][i] = y + s[l[i]];
| ~~~^
Main.cpp:90:10: warning: unused variable 'u' [-Wunused-variable]
90 | int u = __builtin_ctz(x), y = inf;
| ^
Main.cpp:98:15: warning: array subscript has type 'char' [-Wchar-subscripts]
98 | if ((f[l[i]][p[t]].S | mask) == mask)
| ~~~^
Main.cpp:99:40: warning: array subscript has type 'char' [-Wchar-subscripts]
99 | ans = min(ans, dp[mask][i] + f[l[i]][p[t]].F);
| ~~~^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
118104 KB |
Output is correct |
| 2 |
Incorrect |
14 ms |
118024 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
118108 KB |
Output is correct |
| 2 |
Incorrect |
12 ms |
118108 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
118104 KB |
Output is correct |
| 2 |
Incorrect |
14 ms |
118024 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
