oj.uz

Submission #698276

# Submission time Handle Problem Language Result Execution time Memory
698276 2023-02-13T03:06:46 Z vjudge1 Training (IOI07_training) C++17
100 / 100
 14 ms 4692 KB 
/* ...... */

#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 488 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 644 KB Output is correct
2 Correct 1 ms 588 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4656 KB Output is correct
2 Correct 6 ms 4692 KB Output is correct

Subtask #4
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 456 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 468 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 844 KB Output is correct
2 Correct 1 ms 852 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1620 KB Output is correct
2 Correct 1 ms 1620 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2516 KB Output is correct
2 Correct 3 ms 2516 KB Output is correct
3 Correct 4 ms 2516 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4632 KB Output is correct
2 Correct 5 ms 4692 KB Output is correct
3 Correct 4 ms 4692 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2548 KB Output is correct
2 Correct 3 ms 2556 KB Output is correct
3 Correct 14 ms 4664 KB Output is correct
4 Correct 3 ms 2516 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4692 KB Output is correct
2 Correct 14 ms 4692 KB Output is correct
3 Correct 9 ms 4628 KB Output is correct
4 Correct 5 ms 4692 KB Output is correct