Submission #309674

#	Time	Username	Problem	Language	Result	Execution time	Memory
309674		Akashi	Training (IOI07_training)	C++14	30 / 100	1090 ms	836 KiB

training

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

#define x first
#define y second

const int DIM = 1e3 + 5;

struct drum {
	int x, y, c;
};

int n, m;

int tt[DIM], h[DIM], dp[DIM];
bool viz[DIM];
int mark[DIM];
vector <int> arb[DIM];
vector <drum> v[DIM];

vector <int> l;

int lca(int x, int y) {
	while (x != y) {
		if (h[x] > h[y]) x = tt[x];
		else y = tt[y];
	}
	return x;
}

bool mark_road(int nod, int now) {
	if (now == nod) return true;
	l.push_back(now);
	++mark[now];
	if (mark[now] >= 2) return false;
	return mark_road(nod, tt[now]);
}

void unmark_road(int sz) {
	if ((int)l.size() == sz) return ;
	--mark[l.back()];
	l.pop_back();
	unmark_road(sz);
}

void back(int ind, int nod, int end, int sum = 0) {
	if (ind == end) {
		
		for (auto cur : l) {
			
			int ad = 0;
			bool tip = 1;

			for (auto fiu : arb[cur]) {
				if (fiu != tt[cur] && !mark[fiu])
					ad = ad + dp[fiu];
				if (fiu != tt[cur] && mark[fiu]) tip = 0;
			}

			if (tip) sum = sum + max(ad, dp[cur]);
			else sum = sum + ad;
		}

		dp[nod] = max(dp[nod], sum);
		return ;
	}

	int sz = l.size();
	back(ind + 1, nod, end, sum);

	bool ok1 = mark_road(nod, v[nod][ind].x);
	bool ok2 = mark_road(nod, v[nod][ind].y);

	if (ok1 & ok2)
	back(ind + 1, nod, end, sum + v[nod][ind].c);

	unmark_road(sz);
}

void dfs(int nod = 1, int papa = 0) {
	for (auto it : arb[nod]) {
		if (it == papa) continue ;
		h[it] = h[nod] + 1;
		dfs(it, nod);
		tt[it] = nod;
	}
}

void solve(int nod = 1, int papa = 0) {
	for (auto it : arb[nod]) {
		if (it == papa) continue ;
		solve(it, nod);
		dp[nod] += dp[it];
	}

	back(0, nod, v[nod].size(), 0);
}

int main() {
	scanf("%d%d", &n, &m);

	int x, y, c;
	int sum = 0;

	vector <tuple<int, int, int>> edges;

	for (int i = 1; i <= m ; ++i) {
		scanf("%d%d%d", &x, &y, &c);
		
		if (c == 0) {
			arb[x].push_back(y);
			arb[y].push_back(x);
		} else {
			edges.push_back({x, y, c});
		}	
	}

	dfs();
	
	for (auto it : edges) {
		x = get<0>(it);
		y = get<1>(it);
		c = get<2>(it);

		sum += c;

		int z = lca(x, y);
		if ((h[x] - h[z] + h[y] - h[z] + 1) % 2 == 0) continue ;
	
		if (z == x) v[z].push_back({y, z, c});
		else if (z == y) v[z].push_back({x, z, c});
		else v[z].push_back({x, y, c});
	}

	solve();
//	for (int i = 1; i <= n ; ++i) cerr << dp[i] << " ";
//	cerr << endl;
	printf("%d", sum - dp[1]);
	return 0;
}

Compilation message (stderr)

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

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