QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#386989 | #5108. Prehistoric Programs | PetroTarnavskyi# | RE | 0ms | 0kb | C++20 | 1.9kb | 2024-04-11 22:29:08 | 2024-04-11 22:29:08 |
answer
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second
typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;
const int N = 2047;
const int LOG = 14;
LL dist[N][N];
int tin[N][N];
int tout[N][N];
int up[N][LOG][N];
LL mx[N];
LL sum[N];
vector<PII> g[N];
int T;
void dfs(int root, int v, int p)
{
up[root][0][v] = p;
mx[root] = max(mx[root], dist[root][v]);
sum[root] += dist[root][v];
tin[root][v] = T++;
for (auto [to, w] : g[v])
{
if (to != p)
{
dist[root][to] = dist[root][v] + w;
dfs(root, to, v);
}
}
tout[root][v] = T;
}
bool is_anc(int root, int p, int v)
{
return tin[root][p] <= tin[root][v] && tout[root][v] <= tout[root][p];
}
int lca(int root, int u, int v)
{
if (is_anc(root, u, v))
return u;
RFOR (i, LOG, 0)
{
if (!is_anc(root, up[root][i][u], v))
u = up[root][i][u];
}
return up[root][0][u];
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n, q;
cin >> n >> q;
FOR (i, 0, n - 1)
{
int u, v, w;
cin >> u >> v >> w;
u--, v--;
g[u].PB({v, w});
g[v].PB({u, w});
}
FOR (i, 0, n)
{
T = 0;
dfs(i, i, i);
FOR (d, 1, LOG)
FOR (v, 0, n)
up[i][d][v] = up[i][d - 1][up[i][d - 1][v]];
}
FOR (i, 0, q)
{
int s, k, t;
cin >> s >> k >> t;
s--, k--, t--;
cerr << s << ' ' << k << ' ' << t << '\n';
cerr << i << ' ' << lca(k, s, t) << ' ' << lca(t, s, k) << '\n';
if (lca(k, s, t) == k)
cout << 2 * sum[s] - mx[s] << '\n';
else if (lca(t, s, k) == t)
cout << "impossible\n";
else
{
cerr << "other\n";
}
}
return 0;
}
详细
Test #1:
score: 0
Runtime Error
input:
50000 ( ( ))))()))()(()))()()()))()(((((()(((()))()(((()))((()(())))))(()( ) ( ) ((( ( ( ( ( ( () ( ) ( )((())()(( )))))( ( ) )) )() ( ) ) )()( ( ( () ( ) ( )()((((())()))())( ( ( )( ( ( (()())()) ) ) ( ( ( )((())))((())))))))))((((()()))()))))))))((()())())) ) )() ) ) ) ) ) ())(())))))()(()((()(())...