QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#115887 | #5301. Modulo Ruins the Legend | PetroTarnavskyi# | RE | 0ms | 0kb | C++17 | 2.2kb | 2023-06-27 17:42:38 | 2023-06-27 17:42:39 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define FOR(i, a, b) for (int i = (a); i<(b); ++i)
#define RFOR(i, b, a) for (int i = (b)-1; i>=(a); --i)
#define MP make_pair
#define PB push_back
#define F first
#define S second
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int MAGIC = 30;
const int N = 1 << 19;
mt19937 rng;
vector<pair<int, int>> g[N];
LL depth[N];
int tin[N], tout[N], timer;
vector<LL> coefs[MAGIC], prefSum[MAGIC];
LL s[MAGIC];
vector<int> tins;
LL ans = 1e18;
void dfs1(int v, int p) {
tin[v] = timer++;
for (auto [to, w] : g[v]) {
if (to != p) {
depth[to] = depth[v] + w;
dfs1(to, v);
}
}
tout[v] = timer;
}
void dfs2(int v, int p) {
for (auto [to, w] : g[v]) {
if (to != p) {
int l = lower_bound(ALL(tins), tin[to]) - tins.begin(), r = lower_bound(ALL(tins), tout[to]) - tins.begin();
FOR(i, 0, MAGIC) {
s[i] += (prefSum[i].back() - 2 * (prefSum[i][r] - prefSum[i][l])) * w;
}
if (v == 0) {
cerr << (prefSum[0].back() - 2 * (prefSum[0][r] - prefSum[0][l])) * w << endl;
}
dfs2(to, v);
FOR(i, 0, MAGIC) {
s[i] -= (prefSum[i].back() - 2 * (prefSum[i][r] - prefSum[i][l])) * w;
}
}
}
LL d = s[0];
FOR(i, 1, MAGIC) {
d = gcd(d, s[i]);
}
cerr << v << " " << s[0] << endl;
ans = min(ans, s[0] / d);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n, k;
cin >> n >> k;
vector<int> c(k);
for (int& ci : c) {
cin >> ci;
ci--;
}
FOR(i, 0, n - 1) {
int u, v, w;
cin >> u >> v >> w;
u--;
v--;
g[u].emplace_back(v, w);
g[v].emplace_back(u, w);
}
dfs1(0, 0);
sort(ALL(c), [&](int u, int v) {return tin[u] < tin[v];});
for (int ci : c) {
tins.push_back(tin[ci]);
}
coefs[0] = vector<LL>(k, 1);
FOR(i, 1, MAGIC) {
coefs[i].resize(k);
FOR(j, 0, k) {
coefs[i][j] = rng() & 1;
}
}
FOR(i, 0, MAGIC) {
prefSum[i].resize(MAGIC + 1);
FOR(j, 0, k) {
s[i] += coefs[i][j] * depth[c[j]];
prefSum[i][j + 1] = prefSum[i][j] + coefs[i][j];
}
}
dfs2(0, 0);
cout << 2 * ans << "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
input:
6 24 1 1 4 5 1 4