Submission #592394

#	Time	Username	Problem	Language	Result	Execution time	Memory
592394		Mazaalai	Training (IOI07_training)	C++17	82 / 100	1083 ms	22340 KiB

training

#include <bits/stdc++.h>
#define pb push_back
#define ff first
#define ss second
#define sz(a) (int)a.size()
using namespace std;
using PII = pair <int, int>;
const int N = 1001; // maxNode
const int M = 5001; // maxEdge
const int K = 10; // max power of 2 to N, number of children

int n, m;
// solution helper
int cost[M], dp[N][1<<K], lcas[M];
int edgeID[N][N];
// map <int, int> edgeID[N];

vector <PII> edges;
vector <int> intersectingEdges[N];
vector <PII> edgeChildren[M]; // pos, state of children


// lca
int lvl[N];
int jump[N][K+1];
vector <int> paths[N];

void dfs(int pos, int par = 1) {
	jump[pos][0] = par;
	for (auto& el : paths[pos]) {
		if (el == par) continue;
		lvl[el] = lvl[pos]+1;
		dfs(el, pos);
	}
}
int Jump(int a, int b) {
	for (int j = 0; j < K; j++) 
		if (b & (1<<j)) a = jump[a][j];
	return a;
}
int LCA(int a, int b) {
	if (lvl[a] < lvl[b]) swap(a, b);
	a = Jump(a, lvl[a]-lvl[b]);
	if (a == b) return a;
	for (int j = K-1; j >= 0; j--) {
		if (jump[a][j] != jump[b][j]) {
			a = jump[a][j];
			b = jump[b][j];
		}
	}
	return jump[a][0];
}
// tool for debug
string binStr(int s, int p) {
	string res = "";
	while(s > 0) {
		res = res+string(1, ((s&1) + '0'));
		s /= 2;
	}
	while(res.size() < sz(paths[p])) res+="0";
	while(res.size() < 4) res +=".";
	return res;
}

int solve(int pos, int mask = 0) {
	if (pos != 1) mask |= (1<<edgeID[pos][jump[pos][0]]);
	int& res = dp[pos][mask];
	if (res != -1) return res;
	res = 0;
	for (int i = 0; i < sz(paths[pos]); i++) {
		if (mask & (1<<i)) continue;
		res += solve(paths[pos][i]);
	}
	for (auto& intersect : intersectingEdges[pos]) {
		// check if already blocked
		bool blocked = 0;
		int newMask = mask;
		for (int j = sz(edgeChildren[intersect])-2; j < sz(edgeChildren[intersect]); j++) {
			if (mask & (1<<edgeChildren[intersect][j].ss)) blocked = 1;
			newMask |= 1<<edgeChildren[intersect][j].ss;
		}
		if (blocked) continue;
		int cur = cost[intersect] +  solve(pos, newMask);
		for (int j = 0; j < sz(edgeChildren[intersect])-2; j++) {
			PII tmp = edgeChildren[intersect][j];
			cur += solve(tmp.ff, 1<<tmp.ss);
		}
		if (lcas[intersect] != edges[intersect].ff) cur += solve(edges[intersect].ff);
		if (lcas[intersect] != edges[intersect].ss) cur += solve(edges[intersect].ss);
		res = max(res, cur);
	}
	return res;
}
signed main() {
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	// freopen("0.in", "r", stdin);
	// freopen("0.out", "w", stdout);
	cin >> n >> m;
	int mustBlock = 0, sum = 0;
	for (int i = 1; i <= m; i++) {
		int a, b, c; cin >> a >> b >> c;
		if (!c) {
			edgeID[a][b] = sz(paths[a]); paths[a].pb(b);
			edgeID[b][a] = sz(paths[b]); paths[b].pb(a);
		} else {
			cost[sz(edges)] = c;
			edges.pb({a, b});
		}
	}
	dfs(1);
	for (int j = 1; j < K; j++)
	for (int i = 1; i <= n; i++) 
		jump[i][j] = jump[jump[i][j-1]][j-1];

	for (int i = 0; i <= m-n; i++) {
		int a, b; tie(a, b) = edges[i];
		if (lvl[a]%2 != lvl[b]%2) {
			edges[i] = {-1, -1};
			mustBlock += cost[i];
			continue;
		}
		sum += cost[i];
		int lca = LCA(a, b), p;
		lcas[i] = lca;
		if (lvl[a] < lvl[b]) swap(a, b);
		while(lvl[jump[a][0]] > lvl[lca]) {
			p = jump[a][0];
			edgeChildren[i].pb({p, edgeID[p][a]});
			a = p;
		}
		while(lvl[jump[b][0]] > lvl[lca]) {
			p = jump[b][0];
			edgeChildren[i].pb({p, edgeID[p][b]});
			b = p;
		}
		if (b == lca) b = a;
		edgeChildren[i].pb({lca, edgeID[lca][a]});
		edgeChildren[i].pb({lca, edgeID[lca][b]});
		intersectingEdges[lca].pb(i);
	}
	memset(dp, -1, sizeof(dp));
	cout << mustBlock + sum - solve(1) << '\n';
}

Compilation message (stderr)

training.cpp: In function 'std::string binStr(int, int)':
training.cpp:60:19: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   60 |  while(res.size() < sz(paths[p])) res+="0";
      |                   ^

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