QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#300407#7501. Simple Gamedefyers#WA 1ms3984kbC++171.5kb2024-01-08 10:45:212024-01-08 10:45:21

Judging History

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

  • [2024-01-08 10:45:21]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3984kb
  • [2024-01-08 10:45:21]
  • 提交

answer

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

using ll = long long;
using LL = long long;
using pii = pair<int, int>;

struct edge {
	int v, l, c;
};

int n, m;
vector<edge> v[5005];
vector<pair<int, int>> dp[5005];
int robot[5005];

void dfs(int x) {
	for (int i = 0; i <= robot[x]; i++) {
		dp[x].push_back({i, 0});
	}
	if (!v[x].size()) {
		return;
	}
	for (auto i : v[x]) {
		dfs(i.v);
		unordered_map<int, int> M;
		for (auto j : dp[i.v]) {
			if (j.first % 2 != i.c) continue;
			for (auto k : dp[x]) {
				int num = k.first + j.first;
				int cost = k.second + j.second + abs(j.first) * j.second;
				if (M.find(num) != M.end()) {
					M[num] = min(M[num], cost);
				}
				else M[num] = cost;
			}
		}
		dp[x].clear();
		for (auto j : M) {
			dp[x].push_back({j.first, j.second});
		}
	}
}

void solve(int TC) {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		dp[i].clear();
		v[i].clear();
		robot[i] = 0;
	}
	for (int i = 1; i < n; i++) {
		int r1, r2, r3, r4;
		v[r1].push_back({r2, r3, r4});
	}
	for (int i = 1; i <= m; i++) {
		int r1;
		cin >> r1;
		robot[r1]++;
	}
	dfs(1);
	int mn = 1e9;
	for (auto i : dp[1]) {
		if (i.first >= 0) mn = min(mn, i.second);
	}
	if (mn == 1e9) cout << "-1\n";
	else cout << mn << "\n";
	return;
}

int32_t main() {
	cin.tie(0)->sync_with_stdio(0);
	cout << fixed << setprecision(10);

	int t = 1;
	cin >> t;

	for (int i = 1; i <= t; i++) {
		solve(i);
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4
2
1 4
2 1
3
1 1 4
5 1 4
4
1 9 4 9
1 0 0 1
7
3 1 4 1 5 9 2
6 5 3 5 8 9 8

output:

0
0
0
0

result:

wrong answer 1st numbers differ - expected: '5', found: '0'