Submission #937503

#TimeUsernameProblemLanguageResultExecution timeMemory
937503IBoryTraining (IOI07_training)C++17
30 / 100
4 ms1112 KiB
#include <bits/stdc++.h> #define pii pair<int, int> using namespace std; const int MAX = 5005; vector<int> G[MAX], T[MAX]; pii E[MAX]; int P[MAX], D[MAX], C[MAX], dp[MAX], temp[1 << 10]; int in[MAX], out[MAX], dn; void DFS(int cur, int prev) { if (prev) G[cur].erase(find(G[cur].begin(), G[cur].end(), prev)); in[cur] = ++dn; D[cur] = D[prev] + 1; P[cur] = prev; for (int next : G[cur]) DFS(next, cur); out[cur] = dn; } int LCA(int a, int b) { if (D[a] > D[b]) swap(a, b); while (D[a] != D[b]) b = P[b]; while (a != b) a = P[a], b = P[b]; return a; } int Find(int cur, int child) { for (int i = 0; i < G[cur].size(); ++i) { int n = G[cur][i]; if (in[n] <= in[child] && in[child] <= out[n]) return (1 << i); } return 0; } void DFS2(int cur) { for (int next : G[cur]) DFS2(next); vector<pii> cost; for (int i = 0; i < G[cur].size(); ++i) { cost.emplace_back(1 << i, dp[G[cur][i]]); } for (int en : T[cur]) { auto [a, b] = E[en]; int bit = 0, v = C[en]; if (a != cur) bit |= Find(cur, a), v += dp[a]; if (b != cur) bit |= Find(cur, b), v += dp[b]; cost.emplace_back(bit, v); } int Z = (1 << G[cur].size()); memset(temp, 0, sizeof(temp)); for (int i = 0; i < Z; ++i) { for (auto [b, n] : cost) { if (i & b) continue; temp[i | b] = max(temp[i | b], temp[i] + n); } } dp[cur] = *max_element(temp, temp + 1024); } int main() { ios::sync_with_stdio(0); cin.tie(0); int N, M, ans = 0, remain = 1; cin >> N >> M; for (int i = 1; i <= M; ++i) { int a, b, c; cin >> a >> b >> c; if (!c) { G[a].push_back(b); G[b].push_back(a); } else { E[remain] = {a, b}; C[remain++] = c; ans += c; } } DFS(1, 0); for (int i = 1; i <= M - N + 1; ++i) { auto [a, b] = E[i]; if (abs(D[a] - D[b]) & 1) continue; int c = LCA(a, b); T[c].push_back(i); } DFS2(1); ans -= dp[1]; cout << ans; return 0; }

Compilation message (stderr)

training.cpp: In function 'int Find(int, int)':
training.cpp:28:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |  for (int i = 0; i < G[cur].size(); ++i) {
      |                  ~~^~~~~~~~~~~~~~~
training.cpp: In function 'void DFS2(int)':
training.cpp:39:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  for (int i = 0; i < G[cur].size(); ++i) {
      |                  ~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...