QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#392074#5102. Dungeon CrawlernocrizWA 1ms3796kbC++142.3kb2024-04-17 06:11:032024-04-17 06:11:04

Judging History

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

  • [2024-04-17 06:11:04]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3796kb
  • [2024-04-17 06:11:03]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;


int n, q;
vector<pii> G[2020];
vector<pair<pii, int>> query[2020];

int cd = 0;
ll dist[2020], md[2020];
int dfn[2020], sz[2020], ff[2020], depth[2020];
ll ans[200020];
ll tot = 0;
int root;
void dfs(int s, int fa = -1) {
	cd += 1;
	ff[s] = fa;
	dfn[s] = cd;
	sz[s] = 1;
	md[s] = dist[s];
	for(auto ct: G[s]) {
		if(ct.first == fa) continue;
		dist[ct.first] = dist[s] + ct.second;
		depth[ct.first] = depth[s] + 1;
		dfs(ct.first, s);
		md[s] = max(md[s], md[ct.first]);
		sz[s] += sz[ct.first];
	}
}

bool isin(int a, int b) {
	return dfn[a] >= dfn[b] && dfn[a] < dfn[b]+sz[b];
}

ll solve(int t, int k) {
	if(isin(t, k)) {
		return tot*2 - md[root];
	}
	if(isin(k, t)) {
		return -1;
	}
	int ct = t, ck = k;
	while(ff[ct] != ff[ck]) {
		if(depth[ct] > depth[ck]) ct = ff[ct];
		else ck = ff[ck];
	}
	int lca = ff[ct];
	ll ans = 1e18;
	ans = min(ans, tot*2 - md[k]  + 2*(dist[k]-dist[lca]));
	int cp = k;
	while(cp != root) {
		int cf = ff[cp];
		if(depth[cf] >= depth[lca]) {
			for(auto cta: G[cf]) {
				int ct = cta.first;
				if(ct == cp) continue;
				ans = min(ans, tot*2 - md[ct] + 2*(dist[cf]-dist[lca]));
			}
		} else {
			for(auto cta: G[cf]) {
				int ct = cta.first;
				if(ct == cp) continue;
				ans = min(ans, tot*2 - md[ct]);
			}
		}
		cp = cf;
	}
	return ans;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);
	cin>>n>>q;
	for(int i=1;i<n;i++) {
		int u, v, w;
		cin>>u>>v>>w;
		tot += w;
		G[u].push_back(make_pair(v, w));
		G[v].push_back(make_pair(u, w));
	}

	for(int i=0;i<q;i++) {
		int s, k, t;
		cin>>s>>k>>t;
		query[s].push_back(make_pair(make_pair(k, t), i));
	}

	for(int i=1;i<=n;i++) {
		cd = 0;
		memset(dfn, 0, sizeof(dfn));
		memset(dist, 0, sizeof(dist));
		memset(depth, 0, sizeof(depth));
		root = i;
		dfs(i);
		for(auto cq: query[i]) {
			int k = cq.first.first, t = cq.first.second, id = cq.second;
			ans[id] = solve(t, k);
		}
	}

	for(int i=0;i<q;i++) {
		if(ans[i] == -1){
			cout<<"impossible\n";
		} else {
			cout<<ans[i]<<'\n';
		}
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3796kb

input:

22 5
1 2 7
2 3 5
3 4 8
3 6 6
3 7 3
2 5 6
5 8 2
8 9 11
2 10 16
1 11 12
11 12 4
11 13 9
1 14 25
14 15 4
15 16 5
15 17 6
15 18 1
15 19 8
14 20 7
20 21 9
20 22 17
1 19 9
1 9 19
1 8 9
1 9 8
2 22 11

output:

316
293
293
impossible
286

result:

wrong answer 5th lines differ - expected: '314', found: '286'