QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#115892 | #5313. Please Save Pigeland | PetroTarnavskyi# | RE | 5ms | 19816kb | C++17 | 2.0kb | 2023-06-27 17:56:10 | 2023-06-27 17:56:13 |
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 = 100;
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;
}
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]);
}
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(k + 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: 100
Accepted
time: 5ms
memory: 19816kb
input:
5 3 3 4 5 1 2 2 2 3 4 2 5 4 3 4 6
output:
8
result:
ok 1 number(s): "8"
Test #2:
score: 0
Accepted
time: 0ms
memory: 18068kb
input:
10 3 1 7 10 7 6 3 1 8 3 3 6 3 8 6 2 4 1 1 10 6 4 2 8 3 9 10 3 5 10 3
output:
24
result:
ok 1 number(s): "24"
Test #3:
score: -100
Runtime Error
input:
1 1 1