Submission #698276

#	Time	Username	Problem	Language	Result	Execution time	Memory
698276		vjudge1	Training (IOI07_training)	C++17	100 / 100	14 ms	4692 KiB

training

/* ...... */

#include <bits/stdc++.h>
using namespace std;

#define inl inline
typedef long long ll;
typedef pair <int, int> pint;
#define all(p) begin (p), end (p)
#define empb emplace_back
using tint = tuple <int, int, int>;

constexpr int N = 1024, M = 5005;
int n, m, x, y, z, extm, fa[N], dep[N], sid[N];
vector <int> e[N]; tint ext[M];
vector <tint> ex[M]; int tot, f[N][1<<10];

inl void gomx (int &x, const int &y) { if (x < y) x = y; }
void dfs (int x, int fr) {
	fa[x] = fr, dep[x] = dep[fr] + 1;
	int scnt = 0;
	for (const int y : e[x])
		if (y != fr)
			sid[y] = scnt++, dfs (y, x);
	if (fr) e[x].erase (find (all (e[x]), fr));
}
inl int lca (int x, int y) {
	static bool vis[N];
	memset (vis, 0, n + 1);
	while (x) vis[x] = 1, x = fa[x];
	while (!vis[y]) y = fa[y];
	return y;
}
inl pint cost (int l, int x) {
	if (x == l) return { 0, 0 };
	int res = f[x][0];
	while (fa[x] != l)
		res += f[fa[x]][1<<sid[x]], x = fa[x];
	return { 1<<sid[x], res };
}
void dp (int x) {
	vector <pint> lst; int id = 0;
	for (const int y : e[x])
		dp (y), lst.empb (1<<id++, f[y][0]);
	for (const auto [u, v, w] : ex[x]) {
		const auto [s1, c1] = cost (x, v);
		const auto [s2, c2] = cost (x, u);
		lst.empb (s1 | s2, c1 + c2 + w);
	}
	const int siz = e[x].size ();
	memset (f[x], ~0x3f, 1<<12);
	f[x][(1<<siz)-1] = 0;
	for (const auto [msk, w] : lst)
		for (int s = msk; s < 1<<siz; (++s) |= msk)
			gomx (f[x][s^msk], f[x][s] + w);
}

int main () {
	/*  */
	scanf ("%d%d", &n, &m);
	for (int i = 1; i <= m; ++i) {
		scanf ("%d%d%d", &x, &y, &z);
		if (!z) e[x].empb (y), e[y].empb (x);
		else ext[++extm] = { x, y, z }, tot += z;
	}
	dfs (1, 0);
	for (int i = 1; i <= extm; ++i) {
		tie (x, y, z) = ext[i];
		if (dep[x] % 2 != dep[y] % 2);
		else ex[lca (x, y)].empb (ext[i]);
	}
	dp (1); printf ("%d", tot - f[1][0]);

	return 0;
}

Compilation message (stderr)

training.cpp: In function 'int main()':
training.cpp:60:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |  scanf ("%d%d", &n, &m);
      |  ~~~~~~^~~~~~~~~~~~~~~~
training.cpp:62:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |   scanf ("%d%d%d", &x, &y, &z);
      |   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 7 / 7
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 9 / 9
• Subtask 8: 9 / 9
• Subtask 9: 9 / 9
• Subtask 10: 9 / 9
• Subtask 11: 9 / 9