Submission #479154

#TimeUsernameProblemLanguageResultExecution timeMemory
479154JoshcTraining (IOI07_training)C++11
82 / 100
1093 ms17796 KiB
#include <cstdio> #include <vector> #include <algorithm> using namespace std; #define pii pair<int, int> #define mp make_pair #define f first #define s second vector<int> edges[1005], edges2[1005]; vector<pair<int, vector<pii>>> paths[1005]; vector<pair<pii, int>> unpaved; int parent[1005], depth[1005], parity[1005], ind[1005][1005], dp[1005][1024]; void dfs(int v, int p, int d, int t) { parent[v] = p; depth[v] = d; parity[v] = t; for (int i : edges2[v]) { if (i != p) { dfs(i, v, d+1, 1^t); edges[v].push_back(i); } } } int ans(int v, int b) { if (dp[v][b] != -1) return dp[v][b]; dp[v][b] = 0; for (int i : edges[v]) { if ((b&ind[v][i]) == 0) dp[v][b] += ans(i, 0); } for (auto path : paths[v]) { if (b&path.s.back().s) continue; int cur = path.f+ans(v, b^path.s.back().s); for (int i=0; i+1<path.s.size(); i++) cur += ans(path.s[i].f, path.s[i].s); dp[v][b] = max(dp[v][b], cur); } return dp[v][b]; } int main() { int n, m, a, b, c, total = 0; scanf("%d%d", &n, &m); while (m--) { scanf("%d%d%d", &a, &b, &c); total += c; if (c) unpaved.push_back({{a, b}, c}); else { edges2[a].push_back(b); edges2[b].push_back(a); } } dfs(1, 0, 0, 0); for (int i=1; i<=n; i++) { for (int j=0; j<edges[i].size(); j++) ind[i][edges[i][j]] = 1<<j; } for (auto i : unpaved) { a = i.f.f, b = i.f.s, c = i.s; if (parity[a] != parity[b]) continue; if (depth[a] < depth[b]) swap(a, b); vector<pii> path = {{a, 0}}; while (depth[a] != depth[b]) { path.emplace_back(parent[a], ind[parent[a]][a]); a = parent[a]; } if (a != b) { path.emplace_back(b, 0); while (parent[a] != parent[b]) { path.emplace_back(parent[a], ind[parent[a]][a]); a = parent[a]; path.emplace_back(parent[b], ind[parent[b]][b]); b = parent[b]; } path.emplace_back(parent[a], ind[parent[a]][a]^ind[parent[a]][b]); a = parent[a]; } paths[a].emplace_back(c, path); } fill(&dp[0][0], &dp[1004][0], -1); printf("%d\n", total-ans(1, 0)); }

Compilation message (stderr)

training.cpp: In function 'int ans(int, int)':
training.cpp:37:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         for (int i=0; i+1<path.s.size(); i++) cur += ans(path.s[i].f, path.s[i].s);
      |                       ~~~^~~~~~~~~~~~~~
training.cpp: In function 'int main()':
training.cpp:57:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         for (int j=0; j<edges[i].size(); j++) ind[i][edges[i][j]] = 1<<j;
      |                       ~^~~~~~~~~~~~~~~~
training.cpp:45:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
training.cpp:47:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |         scanf("%d%d%d", &a, &b, &c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
#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...