oj.uz

Submission #592394

# Submission time Handle Problem Language Result Execution time Memory
592394 2022-07-09T06:48:38 Z Mazaalai Training (IOI07_training) C++17
82 / 100
 300 ms 22340 KB 
#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

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

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 12116 KB Output is correct
2 Correct 17 ms 12628 KB Output is correct

Subtask #4
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4564 KB Output is correct
2 Correct 3 ms 4564 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4644 KB Output is correct
2 Correct 2 ms 4564 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4820 KB Output is correct
2 Correct 2 ms 4820 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5712 KB Output is correct
2 Correct 3 ms 5716 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6612 KB Output is correct
2 Correct 6 ms 6672 KB Output is correct
3 Correct 92 ms 7124 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 8896 KB Output is correct
2 Correct 31 ms 8404 KB Output is correct
3 Correct 9 ms 8596 KB Output is correct

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 6584 KB Output is correct
2 Correct 7 ms 7636 KB Output is correct
3 Execution timed out 1083 ms 22296 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 12876 KB Output is correct
2 Execution timed out 671 ms 22340 KB Time limit exceeded
3 Halted 0 ms 0 KB -