QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#198972#5208. Jumbled TreescomplexorWA 1ms4076kbC++143.9kb2023-10-03 19:48:282023-10-03 19:48:29

Judging History

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

  • [2023-10-03 19:48:29]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4076kb
  • [2023-10-03 19:48:28]
  • 提交

answer

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <cassert>
#include <numeric>
typedef long long LL; 
typedef std::pair<int, int> pii;
#define MP std::make_pair
#define fi first
#define se second
LL read()
{
	LL s = 0; int f = 1;
	char c = getchar();
	while (!(c >= '0' && c <= '9'))
		f ^= c == '-', c = getchar();
	while (c >= '0' && c <= '9')
		s = s * 10 + (c - '0'), c = getchar();
	return f ? s : -s;
}
const int MAXN = 1005;
int n, m, P, cur = 0;
auto fplus = [](int x, int y){ return x + y >= P ? x + y - P : x + y; };
auto fminus = [](int x, int y){ return x >= y ? x - y : x + P - y; };
int fpow(int x, int y)
{
	int res = 1;
	for (; y; y >>= 1, x = (LL)x * x % P)
		if (y & 1) res = (LL)res * x % P;
	return res;
}
int inv(int x){ return fpow(x, P - 2); }
struct DSU
{
	int fa[MAXN];
	void init(int n){ std::iota(fa + 1, fa + n + 1, 1); }
	int getFath(int x){ return x == fa[x] ? x : (fa[x] = getFath(fa[x])); }
	bool merge(int x, int y)
	{
		x = getFath(x), y = getFath(y);
		return fa[x] = y, (x != y);
	}
} dsu;
struct Edge
{
	int u, v, w;
	Edge(int _u = 0, int _v = 0, int _w = 0)
	: u(_u), v(_v), w(_w) {}
} e[MAXN];
int val[MAXN], D = 0;
std::vector<pii> T[MAXN];
std::vector<int> t[MAXN], node[MAXN];
pii fa[MAXN];
bool vis[MAXN];
void dfs(int x, int fat)
{
	for (pii y : T[x])
		if (y.fi != fat)
			fa[y.fi] = MP(x, y.se), dfs(y.fi, x);
}
int tot, sum, f[MAXN];
void dfs(int x, int fat, int dep)
{
	// printf("|%d %d|\n", x, dep);
	tot++, sum = fplus(sum, e[x].w), vis[x] = true;
	D = std::max(D, dep), node[dep].push_back(x);
	for (int y : t[x])
		if (y != fat) dfs(y, f[y] = x, dep + 1);
}
int ST[2025][MAXN], cnt, ans = 0, vld[2025];
int main()
{
	n = read(), m = read(), P = read();
	for (int i = 1; i <= m; i++)
		e[i].u = read(), e[i].v = read(), e[i].w = read();
	dsu.init(n);
	for (int i = 1; i <= m; i++)
		if (dsu.merge(e[i].u, e[i].v)) 
		{
			T[e[i].u].emplace_back(e[i].v, i);
			T[e[i].v].emplace_back(e[i].u, i);
			vis[i] = true;
		}
	dfs(1, 0);
	dsu.init(m);
	for (int i = 1; i <= m; i++)
		if (!vis[i]) 
		{
			for (int x = e[i].u; x != 1; x = fa[x].fi)
				if (dsu.merge(fa[x].se, i))
					t[fa[x].se].push_back(i), t[i].push_back(fa[x].se);
			for (int x = e[i].v; x != 1; x = fa[x].fi)
				if (dsu.merge(fa[x].se, i))
					t[fa[x].se].push_back(i), t[i].push_back(fa[x].se);
		}
	memset(vis, false, sizeof vis);
	int S = -1;
	for (int i = 1; i <= m; i++) 
		if (!vis[i])
		{
			tot = sum = 0, dfs(i, 0, 0);
			tot = (tot - 1) % P;
			// printf("|%d %d|\n", tot, sum);
			if (tot == 0 && sum != 0)
				return printf("-1\n"), 0;
			else if (tot != 0)
			{
				if (S == -1) S = (LL)sum * inv(tot) % P;
				else if (S != (LL)sum * inv(tot) % P) 
					return printf("-1\n"), 0;
			}
		} 
	if (S != -1)
	{
		vld[++ans] = S, cnt = 0, dsu.init(n);
		for (int i = 1; i <= m; i++)
			if (dsu.merge(e[i].u, e[i].v))
				ST[ans][++cnt] = i, val[i] = fplus(val[i], S);
	}
	for (int i = D; i; i--)
		for (int x : node[i])
		{
			int delt = fminus(e[x].w, val[x]);
			vld[++ans] = delt, ST[ans][cnt = 1] = x;
			dsu.init(n), dsu.merge(e[x].u, e[x].v);
			for (int i = 1; i <= m; i++)
				if (i != x && i != f[x] && dsu.merge(e[i].u, e[i].v))
					ST[ans][++cnt] = i;
			val[x] = fplus(val[x], delt);
			delt = fminus(0, delt);
			vld[++ans] = delt, ST[ans][cnt = 1] = f[x];
			memcpy(ST[ans] + 2, ST[ans - 1] + 2, (n - 2) << 2);
			// dsu.init(n), dsu.merge(e[f[x]].u, e[f[x]].v);
			// for (int i = 1; i <= m; i++)
			// 	if (i != x && i != f[x] && dsu.merge(e[i].u, e[i].v))
			// 		ST[ans][++cnt] = i;
			val[f[x]] = fplus(val[f[x]], delt);
		}
	printf("%d\n", ans);
	for (int i = 1; i <= ans; i++)
	{
		printf("%d ", vld[i]);
		for (int j = 1; j < n; j++)
			printf("%d%c", ST[i][j], " \n"[j == n - 1]);
	}
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3960kb

input:

3 3 101
1 2 30
2 3 40
3 1 50

output:

5
60 1 2
81 2 1
20 3 1
30 3 2
71 1 2

result:

ok Participant found an answer (5 trees) and jury found an answer (5 trees)

Test #2:

score: 0
Accepted
time: 0ms
memory: 4040kb

input:

2 2 37
1 2 8
1 2 15

output:

3
23 1
15 2
22 1

result:

ok Participant found an answer (3 trees) and jury found an answer (3 trees)

Test #3:

score: 0
Accepted
time: 0ms
memory: 3732kb

input:

5 4 5
1 3 1
2 3 2
2 5 3
4 1 4

output:

-1

result:

ok Both jury and participant did not find an answer

Test #4:

score: 0
Accepted
time: 0ms
memory: 3776kb

input:

10 15 997
4 3 459
9 7 94
9 8 767
10 2 877
5 8 258
3 4 166
8 5 621
8 10 619
9 1 316
10 5 516
3 10 125
1 7 961
3 6 500
4 10 976
3 4 842

output:

-1

result:

ok Both jury and participant did not find an answer

Test #5:

score: -100
Wrong Answer
time: 1ms
memory: 4076kb

input:

20 30 9973
1 10 696
3 8 2905
12 7 6609
20 10 1962
11 9 8430
19 2 412
6 3 6936
19 7 9113
14 15 5635
15 7 1770
13 10 3182
3 16 2625
17 1 7387
11 5 3700
9 15 1048
2 3 7717
12 10 8625
7 13 8141
5 14 2245
6 4 2819
18 19 8709
18 5 6191
17 10 7606
9 20 8626
17 4 8848
4 13 1073
10 8 2277
14 2 7714
11 8 5318...

output:

59
296 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 20 21
1666 4 1 2 3 5 6 7 8 9 10 11 12 13 14 15 16 17 20 21
8307 24 1 2 3 5 6 7 8 9 10 11 12 13 14 15 16 17 20 21
2329 12 1 2 3 4 5 6 7 8 9 10 11 13 14 15 16 17 20 21
7644 30 1 2 3 4 5 6 7 8 9 10 11 13 14 15 16 17 20 21
5318 29 1 2 3 4 6 7 8 9 10 11 12...

result:

wrong answer Operation 23 (1-based) is not a tree