| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 795117 |
2023-07-27T06:48:05 Z |
RushB |
LOSTIKS (INOI20_lostiks) |
C++17 |
|
409 ms |
1048576 KB |
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define int int64_t
const int64_t INF = 1ll << 60;
const int N = 1e6 + 5;
const int NWN = 65;
const int M = 20;
int dist[1 << M][NWN], pr[N][M], msk[N][M], h[N], s, t, U[N], V[N], label[N], W[NWN][NWN], MSK[NWN][NWN], n;
bool yes[N];
vector<array<int, 2>> adj[N];
vector<int> key[N];
queue<int> Q[1 << M];
void dfs(int v, int p) {
pr[v][0] = p;
FOR(i, 1, M) {
pr[v][i] = pr[pr[v][i - 1]][i - 1];
msk[v][i] = msk[pr[v][i - 1]][i - 1] | msk[v][i - 1];
}
for (auto P: adj[v]) {
int u = P[0], w = P[1];
if (u == p) continue;
h[u] = h[v] + 1;
msk[u][0] = w;
dfs(u, v);
}
}
array<int, 2> LCA(int u, int v) {
int mask = 0;
if (h[u] > h[v]) swap(u, v);
for (; h[u] != h[v]; v = pr[v][__lg(h[v] - h[u])])
mask |= msk[v][__lg(h[v] - h[u])];
if (u == v)
return {u, mask};
for (int i = M - 1; i >= 0; i--) {
if (pr[v][i] != pr[u][i]) {
mask |= msk[v][i];
mask |= msk[u][i];
v = pr[v][i];
u = pr[u][i];
}
}
assert(pr[v][0] == pr[u][0]);
mask |= msk[u][0];
mask |= msk[v][0];
return {pr[v][0], mask};
}
signed main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> s >> t;
s--;
t--;
int E = 0;
FOR(i, 1, n) {
int u, v, w, ww = 0;
cin >> u >> v >> w;
u--;
v--;
w--;
if (w >= 0) {
yes[u] = yes[v] = yes[w] = true;
U[E] = u;
V[E] = v;
ww = 1 << E;
key[w].push_back(E);
++E;
}
adj[v].push_back({u, ww});
adj[u].push_back({v, ww});
}
dfs(s, s);
vector<int> node;
yes[s] = yes[t] = true;
FOR(i, 0, n) if (yes[i])
node.push_back(i);
FOR(i, 0, node.size()) {
int u = node[i];
label[u] = i;
FOR(j, 0, node.size()) {
int v = node[j];
auto P = LCA(u, v);
W[i][j] = h[u] + h[v] - 2 * h[P[0]];
MSK[i][j] = P[1];
}
}
FOR(i, 0, 1 << M)
fill(dist[i], dist[i] + NWN, INF);
dist[0][label[s]] = 0;
Q[0].push(label[s]);
FOR(i, 0, 1 << M) {
while (Q[i].size()) {
int v = Q[i].front();
Q[i].pop();
for (auto e: key[node[v]]) {
int u = (h[node[U[e]]] < h[node[V[e]]] ? U[e] : V[e]);
if ((MSK[v][u] | i) == i) {
int nwm = i | (1 << e);
if (dist[nwm][u] > dist[i][v] + W[u][v]) {
dist[nwm][u] = dist[i][v] + W[u][v];
Q[nwm].push(u);
}
}
}
FOR(u, 0, node.size()) if ((MSK[v][u] | i) == i) {
if (dist[i][v] + W[v][u] < dist[i][u]) {
dist[i][u] = dist[i][v] + W[v][u];
Q[i].push(u);
}
}
}
}
int mn = INF;
FOR(i, 0, 1 << M)
mn = min(mn, dist[i][label[t]]);
cout << mn << '\n';
}
//09:42:20
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:3:42: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
3 | #define FOR(i, a, b) for (int i = (a); i < (b); i++)
| ^
Main.cpp:80:9: note: in expansion of macro 'FOR'
80 | FOR(i, 0, node.size()) {
| ^~~
Main.cpp:3:42: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
3 | #define FOR(i, a, b) for (int i = (a); i < (b); i++)
| ^
Main.cpp:83:17: note: in expansion of macro 'FOR'
83 | FOR(j, 0, node.size()) {
| ^~~
Main.cpp:3:42: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
3 | #define FOR(i, a, b) for (int i = (a); i < (b); i++)
| ^
Main.cpp:108:25: note: in expansion of macro 'FOR'
108 | FOR(u, 0, node.size()) if ((MSK[v][u] | i) == i) {
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
409 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
363 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
409 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
