Submission #1165655

#TimeUsernameProblemLanguageResultExecution timeMemory
1165655InvMODTraining (IOI07_training)C++20
100 / 100
4 ms840 KiB
#include <bits/stdc++.h> using namespace std; #define fi first #define se second #define gcd __gcd #define sz(v) (int) v.size() #define pb push_back #define pi pair<int,int> #define all(v) (v).begin(), (v).end() #define compact(v) (v).erase(unique(all(v)), (v).end()) #define FOR(i, a, b) for(int i = (a); i <= (b); i++) #define REV(i, a, b) for(int i = (a); i >= (b); i--) #define dbg(x) "[" #x " = " << (x) << "]" ///#define int long long using ll = long long; using ld = long double; using ull = unsigned long long; template<typename T> bool ckmx(T& a, const T& b){if(a < b) return a = b, true; return false;} template<typename T> bool ckmn(T& a, const T& b){if(a > b) return a = b, true; return false;} const int N = 2e5+5; const ll MOD = 1e9+7; const ll INF = 1e18; struct Edge{ int u,v; ll w; Edge(int u = 0, int v = 0, ll w = 0): u(u), v(v), w(w) {} bool operator < (const Edge& q) const{ return w < q.w; }; }; void solve() { int n,m; cin >> n >> m; vector<Edge> E(m + 1); FOR(i, 1, m){ int u,v,w; cin >> u >> v >> w; E[i] = Edge(u, v, w); } sort(1 + all(E)); vector<vector<int>> adj(n + 1, vector<int>()); FOR(i, 1, m){ if(!E[i].w){ int u = E[i].u, v = E[i].v; adj[u].pb(v), adj[v].pb(u); } } const int lg = 12; vector<int> h(n + 1), idChild(n + 1); vector<vector<int>> child(n + 1, vector<int>()); vector<vector<int>> par(lg, vector<int>(n + 1)); function<void(int,int)> preDFS = [&](int x, int p) -> void{ for(int v : adj[x])if(v != p) child[x].push_back(v); for(int j = 0; j < sz(child[x]); j++){ int v = child[x][j]; par[0][v] = x; for(int i = 1; i < lg; i++){ par[i][v] = par[i - 1][par[i - 1][v]]; } h[v] = h[x] + 1; idChild[v] = j; preDFS(v, x); } return; }; preDFS(1, -1); auto bjump = [&](int u, int dist) -> int{ for(int i = lg - 1; i >= 0; i--){ if(dist >> i & 1){ u = par[i][u]; } } return u; }; auto get_LCA = [&](int u, int v) -> int{ if(h[u] < h[v]) swap(u, v); u = bjump(u, h[u] - h[v]); if(u == v) return v; for(int i = lg - 1; i >= 0; i--){ if(par[i][u] != par[i][v]){ u = par[i][u]; v = par[i][v]; } } return par[0][v]; }; vector<vector<Edge>> Query(n + 1, vector<Edge>()); ll total = 0; FOR(i, 1, m){ if(E[i].w){ int u = E[i].u, v = E[i].v; int lca = get_LCA(u, v); int dist = h[u] + h[v] - 2 * h[lca]; if(!(dist & 1)){ Query[lca].push_back(E[i]); //cout << u <<" " << v <<" " << E[i].w << "\n"; } } total = total + E[i].w; } vector<vector<ll>> dp(n + 1, vector<ll>()); auto fmask = [&](int u) -> int{ return (1 << sz(child[u])) - 1; }; auto calc = [&](int x, int fa) -> ll{ if(x == fa) return 0; ll answer = dp[x][fmask(x)]; while(par[0][x] != fa){ int u = par[0][x]; int curID = fmask(u) ^ (1 << idChild[x]); answer = answer + dp[u][curID]; x = u; } return answer; }; function<void(int,int)> calc_dp = [&](int x, int p) -> void{ dp[x].assign(fmask(x) + 1, 0); for(int v : child[x]){ calc_dp(v, x); for(int msk = (1 << idChild[v]); msk <= fmask(x); msk++, msk |= (1 << idChild[v])){ dp[x][msk] = max(dp[x][msk], dp[x][msk ^ (1 << idChild[v])] + dp[v][fmask(v)]); } } for(Edge& e : Query[x]){ int u = e.u, v = e.v; ll tmp = e.w; int maskChoosed = 0; if(u != x){ tmp = tmp + calc(u, x); int paru = bjump(u, h[u] - h[x] - 1); maskChoosed = maskChoosed | (1 << idChild[paru]); } if(v != x){ tmp = tmp + calc(v, x); int parv = bjump(v, h[v] - h[x] - 1); maskChoosed = maskChoosed | (1 << idChild[parv]); } for(int msk = maskChoosed; msk <= fmask(x); msk++, msk |= maskChoosed){ dp[x][msk] = max(dp[x][msk], dp[x][msk ^ maskChoosed] + tmp); } } return; }; calc_dp(1, -1); cout << total - dp[1][fmask(1)] << "\n"; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define name "InvMOD" if(fopen(name".INP", "r")){ freopen(name".INP","r",stdin); freopen(name".OUT","w",stdout); } int t = 1; //cin >> t; while(t--) solve(); return 0; }

Compilation message (stderr)

training.cpp: In function 'int main()':
training.cpp:192:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  192 |         freopen(name".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
training.cpp:193:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  193 |         freopen(name".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...