Submission #58871

#	Time	Username	Problem	Language	Result	Execution time	Memory
58871		memikakizaki	Training (IOI07_training)	C++14	100 / 100	22 ms	5524 KiB

training

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3+1, M = 5e3+1;
inline void setmax(int &a, int b) { if(b > a) a = b; }

int n, m, sum, upar[M], vpar[M];
vector<tuple<int,int,int> > unpaved;
vector<int> g[N], ls[N];

int d[N];
vector<int> anc[N];
void init_lca(int u, int par) {
	for(int v: g[u]) if(v != par) {
		d[v] = d[u] + 1;
		anc[v].push_back(u);
		for(int j = 0; 1 << j+1 <= d[v]; j++) anc[v].push_back(anc[anc[v][j]][j]);
		init_lca(v, u);
	}
}
int get_lca(int u, int v) {
	if(d[u] < d[v]) swap(u, v);
	for(int j = 0; d[u] > d[v]; j++) if(d[u] - d[v] >> j & 1) u = anc[u][j];
	if(u == v) return u;
	for(int j = 10; j >= 0; j--) if(j < anc[u].size() && anc[u][j] != anc[v][j])
		u = anc[u][j], v = anc[v][j];
	return anc[u][0];
}
int get_par(int u, int dist) {
	for(int j = 0; 1 << j <= dist; j++) if(dist >> j & 1) u = anc[u][j];
	return u;
}

int dp[N][N];

int rt1, rt2, val;
void rec_vals(int u, int par) {
	setmax(dp[rt1][u], dp[rt2][u] + val);
	for(int v: g[u]) if(v != par) rec_vals(v, u);
}

void dfs(int u, int par) {
	vector<int> ord;
	for(int v: g[u]) if(v != par) {
		dfs(v, u);
		ord.push_back(v);
	}
	vector<int> f(1 << ord.size());
	map<int, int> rev;
	for(int i = 0; i < ord.size(); i++) {
		rev[ord[i]] = i;
		setmax(f[1 << i], dp[ord[i]][ord[i]]);
	}
	for(int idx: ls[u]) {
		int x, y, w; tie(x, y, w) = unpaved[idx];
		// cout << u << ' ' << x << ' ' << y << ' ' << upar[idx] << ' ' << vpar[idx] << ' ' << w << endl;
		if(y == u) {
			setmax(f[(1 << rev[upar[idx]])], dp[upar[idx]][x] + w);
		} else {
			setmax(f[(1 << rev[upar[idx]]) | (1 << rev[vpar[idx]])], dp[upar[idx]][x] + dp[vpar[idx]][y] + w);
		}
	}
	for(int mask = 1; mask < 1 << ord.size(); mask++) {
		int lowbit = mask & -mask;
		setmax(f[mask], f[mask ^ lowbit] + f[lowbit]);
		if(!(mask ^ lowbit)) continue;
		for(int i = 0; i < ord.size(); i++) if(1 << i != lowbit && (mask >> i & 1)) {
			setmax(f[mask], f[mask ^ lowbit ^ (1 << i)] + f[lowbit | (1 << i)]);
		}
	}
	// cout << u << endl;
	// for(int i = 0; i < 1 << ord.size(); i++) cout << i << ' ' << f[i] << endl;
	rt1 = u;
	for(int i = 0; i < ord.size(); i++) {
		rt2 = ord[i];
		val = f[((1 << ord.size()) - 1) ^ (1 << i)];
		rec_vals(ord[i], u);
	}
	dp[u][u] = f[(1 << ord.size()) - 1];
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	for(int i = 0, u, v, w; i < m; i++) {
		cin >> u >> v >> w;
		if(!w) g[u].push_back(v), g[v].push_back(u);
		else unpaved.emplace_back(u, v, w);
		sum += w;
	}
	init_lca(1, 0);
	vector<tuple<int,int,int> > tmp;
	for(auto tt: unpaved) {
		int u, v, w;
		tie(u, v, w) = tt;
		if(d[u] < d[v]) swap(u, v); // make sure only one possible == lca
		int lca = get_lca(u, v);
		if(d[u] + d[v] - 2*d[lca] & 1) continue;
		int i = tmp.size();
		ls[lca].push_back(i);
		if(u != lca) upar[i] = get_par(u, d[u] - d[lca] - 1);
		if(v != lca) vpar[i] = get_par(v, d[v] - d[lca] - 1);
		tmp.emplace_back(u, v, w);
	}
	unpaved = tmp;
	dfs(1, 0);
	cout << sum - dp[1][1];
}

Compilation message (stderr)

training.cpp: In function 'void init_lca(int, int)':
training.cpp:16:24: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   for(int j = 0; 1 << j+1 <= d[v]; j++) anc[v].push_back(anc[anc[v][j]][j]);
                       ~^~
training.cpp: In function 'int get_lca(int, int)':
training.cpp:22:43: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
  for(int j = 0; d[u] > d[v]; j++) if(d[u] - d[v] >> j & 1) u = anc[u][j];
                                      ~~~~~^~~~~~
training.cpp:24:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j = 10; j >= 0; j--) if(j < anc[u].size() && anc[u][j] != anc[v][j])
                                  ~~^~~~~~~~~~~~~~~
training.cpp: In function 'void dfs(int, int)':
training.cpp:49:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < ord.size(); i++) {
                 ~~^~~~~~~~~~~~
training.cpp:66:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < ord.size(); i++) if(1 << i != lowbit && (mask >> i & 1)) {
                  ~~^~~~~~~~~~~~
training.cpp:73:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < ord.size(); i++) {
                 ~~^~~~~~~~~~~~
training.cpp: In function 'int main()':
training.cpp:98:18: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   if(d[u] + d[v] - 2*d[lca] & 1) continue;
      ~~~~~~~~~~~~^~~~~~~~~~

• 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: 9 / 9
• Subtask 11: 9 / 9