Submission #309671

#	Time	Username	Problem	Language	Result	Execution time	Memory
309671		Akashi	Training (IOI07_training)	C++14	0 / 100	21 ms	640 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 <pair <int, int>> v[DIM];
vector <drum> path[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) {
			for (auto fiu : arb[cur]) {
				if (fiu != tt[cur] && !mark[fiu])
					sum = sum + dp[fiu];
			}
		}

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

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

	bool ok = mark_road(nod, v[nod][ind].x);
	if (ok)
	back(ind + 1, nod, end, sum + v[nod][ind].y);

	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);
	for (auto it : path[nod]) {
		mark_road(nod, it.x); mark_road(nod, it.y);
		back(0, nod, v[nod].size(), it.c + dp[it.x] + dp[it.y]);
		unmark_road(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, c});
		else if (z == y) v[z].push_back({x, c});
		else 	path[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:95:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   95 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
training.cpp:103:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  103 |   scanf("%d%d%d", &x, &y, &c);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 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