QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#115887#5301. Modulo Ruins the LegendPetroTarnavskyi#RE 0ms0kbC++172.2kb2023-06-27 17:42:382023-06-27 17:42:39

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-27 17:42:39]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2023-06-27 17:42:38]
  • 提交

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

output:


result: