Submission #1042377

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042377		ef10	Training (IOI07_training)	C++17	17 / 100	23 ms	15964 KiB

training

// Source: https://usaco.guide/general/io

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

#define LL long long

struct edge {
	int root;
	vector<int> children;
	int a;
	int b;
	int c;
};

struct node {
	int p;
	int d;
	int i;
};

auto cmp = [](const edge& a, const edge& b) {
		if (a.root < b.root) return true;
		if (a.root > b.root) return false;
		if (a.c < b.c) return true;
		if (a.c > b.c) return false;
		if (a.a < b.a) return true;
		if (a.a > b.a) return false;
		if (a.b < b.b) return true;
		if (a.b > b.b) return false;
		return false; 
	};

node A[1005];

int N, M;
vector<int> adj[1005];
vector<edge> edges;
LL dp[1005][1<<11];
bool done[1005][1<<11];

void findcommon(edge& e) {
	node a = A[e.a];
	node b = A[e.b];
	if (a.d > b.d) {
		node t;
		t = a;
		a = b;
		b = t;
	}
	while (b.d > a.d) {
		if (b.p == a.i) {
			e.root = a.i;
			e.children.push_back(b.i);
			return;
		}
		b = A[b.p];
	}
	while (true) {
		if (b.p == a.p) {
			e.root = b.p;
			e.children.push_back(b.i);
			e.children.push_back(a.i);
			return;
		}
		b = A[b.p];
		a = A[a.p];
	}
}

void solve(int r, int mask) {
	if (done[r][mask]) return;
	done[r][mask] = true;
	if (mask == 0 || (__builtin_popcount(mask) == 1 && r != 0)) return;
	LL res = 0;
	for (int i = 0; i < adj[r].size(); i++) {
		if (adj[r][i]==A[r].p) continue;
		if ((mask & (1<<i)) == 0) continue;
		int n = adj[r][i];
		solve(n, ((1<<adj[n].size())-1));
		res += dp[n][(1<<adj[n].size())-1];
	}
	//cout << r << "/" << mask << ", res: " << res << endl;
	edge e; e.root = r; e.a=0;e.b=0;e.c=0;
	auto it = lower_bound(edges.begin(), edges.end(), e, cmp);
	while (it!= edges.end() && it->root == r) {
		int cmask = 0;
		for (auto c : it->children) {
			auto ind = lower_bound(adj[r].begin(),adj[r].end(),c)-adj[r].begin();
			cmask |= (1<<ind);
		}
		if ((cmask & mask) != cmask) {
			it++;
			 continue;
		}
		bool visited[N]; memset(visited,0,sizeof(visited));
		LL current = it->c;
		for (int i = 0; i < 2; i++) {
			int n = (i==0) ? it->a : it->b;
			int p = -1;
			while (n != r) {
				int nmask = (1 << (adj[n].size())) - 1;
				if (p>=0) {
					auto indp = lower_bound(adj[n].begin(),adj[n].end(),p)-adj[n].begin();
					nmask &= ~(1<<indp);
				}
				solve(n,nmask);
				current += dp[n][nmask];
				//cout << "1current + dp["<<n<<"]["<<nmask<<"] = " << dp[n][nmask] << endl;
				visited[n] = true;
				p = n;
				n = A[n].p;
			}
		}
		int rmask = mask & ~cmask;
		solve(r,rmask);
		current += dp[r][rmask];
				//cout << "2current + dp["<<r<<"]["<<rmask<<"] = " << dp[r][rmask] << endl;
		for (int i = 0; i < adj[r].size(); i++) {
			if (adj[r][i] == A[r].p) continue;
			if (!(rmask & (1<<i))) continue;
			int n = adj[r][i];
			if (visited[n]) continue;
			solve(n,(1<<adj[n].size())-1);
			current += dp[n][(1<<adj[n].size())-1];
		}
		//cout <<  r << "/" << mask << ", edge: " << it->a << "/" << it->b << "/" << it->c << ", current: " << current << endl;
		if (current > res) {
			res = current;
		}
		it++;
	}
	dp[r][mask] = res;
	//cout << "dp["<<r<<"]["<<mask<<"] = " << res << endl;
}

void dfs(int r, int p) {
	if (p >= 0) {
		A[r].d = A[p].d + 1;
	}
	A[r].p = p;
	for (auto e : adj[r]) {
		if (e == p) continue;
		dfs(e, r);
	}
}

int main() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		A[i].i = i;
	}
	vector<edge> es;
	LL totalc = 0;
	for (int i = 0; i < M; i++) {
		int a,b, c; cin >> a >> b >> c; a--; b--;
		totalc += c;
		if (c == 0) {
			adj[a].push_back(b);
			adj[b].push_back(a);
		} else {
			es.push_back(edge({-1,{},a,b,c}));
		}
	}
	for (int i = 0; i < N; i++) {
		sort(adj[i].begin(),adj[i].end());
	}
	dfs(0, -1);
	for (auto e : es) {
		if (((A[e.a].d + A[e.b].d) % 2) == 0) {
			edges.push_back(e);
		}
	}
	for (auto& e : edges) {
		findcommon(e);
	}
	sort(edges.begin(),edges.end(), cmp);
	solve(0, (1<<adj[0].size())-1);
	cout << totalc-dp[0][(1<<adj[0].size())-1] << endl;
}

Compilation message (stderr)

training.cpp: In function 'void solve(int, int)':
training.cpp:76:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |  for (int i = 0; i < adj[r].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~
training.cpp:119:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |   for (int i = 0; i < adj[r].size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~

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