oj.uz

답안 #592381

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
592381 2022-07-09T06:35:23 Z Mazaalai Training (IOI07_training) C++17
82 / 100
 300 ms 18760 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];
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];
}
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;
		for (int j = sz(edgeChildren[intersect])-2; j < sz(edgeChildren[intersect]); j++) {
			if (mask & (1<<edgeChildren[intersect][j].ss)) blocked = 1;
		}
		if (blocked) continue;
		int cur = cost[intersect];
		for (int j = 0; j < sz(edgeChildren[intersect])-2; j++) {
			PII tmp = edgeChildren[intersect][j];
			int newMask = (1<<tmp.ss);
			cur += solve(tmp.ff, newMask);
		}
		int newMask = mask;
		for (int j = sz(edgeChildren[intersect])-2; j < sz(edgeChildren[intersect]); j++) {
			newMask |= 1<<edgeChildren[intersect][j].ss;
		}
		cur += solve(pos, newMask);
		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);
	}
	// cout << pos << " " << binStr(mask, pos) << ": " << res << '\n';
	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;
		p = jump[a][0];
		edgeChildren[i].pb({p, edgeID[p][a]});
		p = jump[b][0];
		edgeChildren[i].pb({p, edgeID[p][b]});
		intersectingEdges[lca].pb(i);
		// for (auto [a, b] : edgeChildren[i]) cout << a << "," << b << ',' << paths[a][b] << "  "; cout << "\n";
	}
	memset(dp, -1, sizeof(dp));
	cout << mustBlock + sum - solve(1) << '\n';
}

Compilation message

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

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4564 KB Output is correct
2 Correct 2 ms 4564 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 8532 KB Output is correct
2 Correct 20 ms 9060 KB Output is correct

Subtask #4
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4436 KB Output is correct
2 Correct 2 ms 4436 KB Output is correct

Subtask #5
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4564 KB Output is correct
2 Correct 4 ms 4564 KB Output is correct

Subtask #6
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4564 KB Output is correct
2 Correct 2 ms 4564 KB Output is correct

Subtask #7
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4564 KB Output is correct
2 Correct 3 ms 4648 KB Output is correct

Subtask #8
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 4864 KB Output is correct
2 Correct 7 ms 4820 KB Output is correct
3 Correct 148 ms 5392 KB Output is correct

Subtask #9
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 5556 KB Output is correct
2 Correct 44 ms 5072 KB Output is correct
3 Correct 12 ms 5204 KB Output is correct

Subtask #10
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 4804 KB Output is correct
2 Correct 8 ms 5808 KB Output is correct
3 Execution timed out 1086 ms 18508 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #11
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 9300 KB Output is correct
2 Execution timed out 1087 ms 18760 KB Time limit exceeded
3 Halted 0 ms 0 KB -