Submission #487066

#TimeUsernameProblemLanguageResultExecution timeMemory
487066XIITraining (IOI07_training)C++17
100 / 100
9 ms2564 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define fi first #define se second #define mp make_pair #define eb emplace_back #define ALL(x) (x).begin(), (x).end() #define FOR(i, a, b) for(int i = (a); i < (b); ++i) #define FORU(i, a, b) for(int i = (a); i <= (b); ++i) #define FORD(i, a, b) for(int i = (a); i >= (b); --i) #define IOS cin.tie(0)->sync_with_stdio(false); #define PROB "IOI07_training" void Fi(){ if(fopen(PROB".inp", "r")){ freopen(PROB".inp", "r", stdin); freopen(PROB".out", "w", stdout); } } const int N = 1e3 + 1; int n, m; vector<int> adj[N]; int h[N], finish[N], leaveTime; using pi = pair<int, int>; pi p[N]; struct edge{ int u, v, w; int lca; const bool operator<(const edge &ot){ return finish[lca] < finish[ot.lca]; } }; vector<edge> ed; vector<edge> pass[N]; int totCost = 0; void enter(){ cin >> n >> m; ed.resize(m); for(auto &x: ed){ cin >> x.u >> x.v >> x.w; if(!x.w){ adj[x.u].eb(x.v); adj[x.v].eb(x.u); } else totCost += x.w; } } void dfs(int u){ FOR(i, 0, adj[u].size() - 1){ if(adj[u][i] == p[u].fi){ swap(adj[u][i], adj[u][adj[u].size() - 1]); break; } } /// adj[u].back() is parent of u FOR(i, 0, adj[u].size() - 1){ int v = adj[u][i]; h[v] = h[u] + 1; p[v] = {u, 1 << i}; dfs(v); } finish[u] = ++leaveTime; } void calcLCA(){ for(auto &E: ed){ int u = E.u, v = E.v; if(h[u] < h[v]) swap(u, v); while(h[u] != h[v]) u = p[u].fi; while(p[u].fi != p[v].fi){ u = p[u].fi; v = p[v].fi; } E.lca = (u == v ? u : p[u].fi); } } void init(){ adj[1].eb(0); dfs(1); calcLCA(); sort(ALL(ed)); } int dp[N][1 << 9]; void solve(){ for(auto E: ed){ int L = (h[E.lca] - h[E.u]) + (h[E.lca] - h[E.v]); if(E.w && (L & 1)) continue; int V = E.lca; pi u = {E.u, 0}, v = {E.v, 0}; int tmp = E.w; while(u.fi != V){ tmp += dp[u.fi][u.se]; u = p[u.fi]; } while(v.fi != V){ tmp += dp[v.fi][v.se]; v = p[v.fi]; } int N = adj[V].size() - 1; // cout << E.u << " " << E.v << " " << E.w << " " << V << ": "; // cout << N << " " << tmp << "\n"; FORD(mask, (1 << N) - 1, 0){ if((mask & u.se) || (mask & v.se)) continue; dp[V][mask] = max(dp[V][mask], tmp + dp[V][mask | u.se | v.se]); } } } int main(){ IOS; Fi(); enter(); init(); solve(); cout << totCost - dp[1][0]; return 0; }

Compilation message (stderr)

training.cpp: In function 'void dfs(int)':
training.cpp:12:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define FOR(i, a, b) for(int i = (a); i < (b); ++i)
      |                                         ^
training.cpp:56:5: note: in expansion of macro 'FOR'
   56 |     FOR(i, 0, adj[u].size() - 1){
      |     ^~~
training.cpp:12:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define FOR(i, a, b) for(int i = (a); i < (b); ++i)
      |                                         ^
training.cpp:62:5: note: in expansion of macro 'FOR'
   62 |     FOR(i, 0, adj[u].size() - 1){
      |     ^~~
training.cpp: In function 'void Fi()':
training.cpp:20:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |         freopen(PROB".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
training.cpp:21:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         freopen(PROB".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#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...