QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#386989#5108. Prehistoric ProgramsPetroTarnavskyi#RE 0ms0kbC++201.9kb2024-04-11 22:29:082024-04-11 22:29:08

Judging History

你现在查看的是最新测评结果

  • [2024-04-11 22:29:08]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [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
(
(
))))()))()(()))()()()))()(((((()(((()))()(((()))((()(())))))(()(
)
(
)
(((
(
(
(
(
(
()
(
)
(
)((())()((
)))))(
(
)
))
)()
(
)
)
)()(
(
(
()
(
)
(
)()((((())()))())(
(
(
)(
(
(
(()())())
)
)
(
(
(
)((())))((())))))))))((((()()))()))))))))((()())()))
)
)()
)
)
)
)
)
())(())))))()(()((()(())...

output:


result: