Submission #720168

#TimeUsernameProblemLanguageResultExecution timeMemory
720168marvinthangTraining (IOI07_training)C++17
100 / 100
8 ms732 KiB
/************************************* * author: marvinthang * * created: 23.08.2022 19:01:09 * *************************************/ #include <bits/stdc++.h> using namespace std; #define fi first #define se second #define div ___div #define left ___left #define right ___right #define TIME (1.0 * clock() / CLOCKS_PER_SEC) #define MASK(i) (1LL << (i)) #define FULL(i) (MASK(i) - 1) #define BIT(x, i) ((x) >> (i) & 1) #define __builtin_popcount __builtin_popcountll #define scan_op(...) istream & operator >> (istream &in, __VA_ARGS__ &u) #define print_op(...) ostream & operator << (ostream &out, const __VA_ARGS__ &u) #define file(name) if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); } template <class T> scan_op(vector <T>) { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; } template <class T> print_op(vector <T>) { out << '{'; for (size_t i = 0; i + 1 < u.size(); ++i) out << u[i] << ", "; if (!u.empty()) out << u.back(); return out << '}'; } template <class U, class V> scan_op(pair <U, V>) { return in >> u.fi >> u.se; } template <class U, class V> print_op(pair <U, V>) { return out << '(' << u.fi << ", " << u.se << ')'; } template <class A, class B> inline bool minimize(A &a, B b) { A eps = 1e-9; if (a > b + eps) { a = b; return true; } return false; } template <class A, class B> inline bool maximize(A &a, B b) { A eps = 1e-9; if (a + eps < b) { a = b; return true; } return false; } const double PI = 3.1415926535897932384626433832795; // acos(-1.0); atan(-1.0); const int dir[] = {1, 0, -1, 0, 1, 1, -1, -1, 1}; // {2, 1, -2, -1, -2, 1, 2, -1, 2}; const int MAX = 1002; struct Edge { int u, v, c; Edge(int u, int v, int c): u(u), v(v), c(c) {} }; int numNode, numEdge; vector <int> adj[MAX]; vector <Edge> edges; void init(void) { cin >> numNode >> numEdge; while (numEdge--) { int u, v, c; cin >> u >> v >> c; if (c) edges.push_back(Edge(u, v, c)); else { adj[u].push_back(v); adj[v].push_back(u); } } } int deg[MAX], depth[MAX]; pair <int, int> par[MAX]; void dfs(int u) { depth[u] = depth[par[u].fi] + 1; for (int v: adj[u]) if (v != par[u].fi) { par[v] = make_pair(u, MASK(deg[u]++)); dfs(v); } } vector <Edge> listEdge[MAX]; int initEdge(void) { int sum = 0; for (int i = edges.size(); i--; ) { sum += edges[i].c; bool color = 0; int u = edges[i].u, v = edges[i].v; while (u != v) { if (depth[u] < depth[v]) swap(u, v); u = par[u].fi; color ^= 1; } if (color) { swap(edges[i], edges.back()); edges.pop_back(); continue; } listEdge[u].push_back(edges[i]); } return sum; } int *F[MAX]; void dp(int u) { F[u] = new int[MASK(deg[u])]; fill(F[u], F[u] + MASK(deg[u]), 0); for (int v: adj[u]) if (v != par[u].fi) { dp(v); for (int mask = MASK(deg[u]); mask--; ) if (!(mask & par[v].se)) maximize(F[u][mask], F[v][0] + F[u][mask ^ par[v].se]); } for (auto [w1, w2, c]: listEdge[u]) { int sum = c; pair <int, int> v1, v2; for (v1 = make_pair(w1, 0); v1.fi != u; v1 = par[v1.fi]) sum += F[v1.fi][v1.se]; for (v2 = make_pair(w2, 0); v2.fi != u; v2 = par[v2.fi]) sum += F[v2.fi][v2.se]; for (int mask = MASK(deg[u]); mask--; ) if (!(mask & v1.se) && !(mask & v2.se)) maximize(F[u][mask], sum + F[u][mask ^ v1.se ^ v2.se]); } } void process(void) { dfs(1); int total = initEdge(); dp(1); cout << total - F[1][0] << '\n'; } int main(void) { ios_base::sync_with_stdio(false); cin.tie(nullptr); // cout.tie(nullptr); file("training"); init(); process(); cerr << "Time elapsed: " << TIME << " s.\n"; return (0^0); }

Compilation message (stderr)

training.cpp: In function 'int main()':
training.cpp:22:69: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 | #define          file(name)  if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }
      |                                                             ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
training.cpp:121:2: note: in expansion of macro 'file'
  121 |  file("training");
      |  ^~~~
training.cpp:22:103: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 | #define          file(name)  if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }
      |                                                                                               ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
training.cpp:121:2: note: in expansion of macro 'file'
  121 |  file("training");
      |  ^~~~
#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...