QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#198965 | #5208. Jumbled Trees | complexor | RE | 1ms | 6024kb | C++14 | 3.7kb | 2023-10-03 19:43:01 | 2023-10-03 19:43:01 |
Judging History
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)
{
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);
for (int i = 1; i <= m; i++)
if (!vis[i])
{
for (int x = e[i].u; x != 1; x = fa[x].fi)
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)
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: 6024kb
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: 3920kb
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: 3768kb
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: -100
Runtime Error
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