oj.uz

Submission #1042377

# Submission time Handle Problem Language Result Execution time Memory
1042377 2024-08-03T03:08:02 Z ef10 Training (IOI07_training) C++17
17 / 100
 23 ms 15964 KB 
// 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

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

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2652 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 15964 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
7.0 / 7.0

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

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2652 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1372 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 4596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 2160 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 6388 KB Output isn't correct
2 Halted 0 ms 0 KB -