Submission #761192

#TimeUsernameProblemLanguageResultExecution timeMemory
761192nononoTraining (IOI07_training)C++14
100 / 100
61 ms8628 KiB
#include "bits/stdc++.h" #define SZ(x) (int)(x.size()) using namespace std; const int mxN = 1005; int n, m; vector<vector<int>> adj(mxN); vector<vector<array<int, 3>>> k(mxN); vector<array<int, 3>> edge; int h[mxN], up[mxN][11]; int id[mxN][mxN]; int dp[mxN][1 << 10], f[mxN]; void dfs(int u, int p){ up[u][0] = p; for(int i = 1; i <= 10; i ++){ up[u][i] = up[up[u][i - 1]][i - 1]; } int Time = 0; for(int v : adj[u]){ if(v == p) continue ; id[u][v] = Time ++ ; h[v] = h[u] + 1; dfs(v, u); } } int get_LCA(int u, int v){ if(h[u] < h[v]) swap(u, v); int depth = h[u] - h[v]; for(int i = 0; i <= 10; i ++){ if(depth >> i & 1){ u = up[u][i]; } } if(u == v) return u; for(int i = 10; i >= 0; i --){ if(up[u][i] != up[v][i]){ u = up[u][i]; v = up[v][i]; } } return up[u][0]; } int jump(int u, int x){ if(x < 0) return u; for(int i = 0; i <= 10; i ++){ if(x >> i & 1){ u = up[u][i]; } } return u; } void update(int u, int p){ for(int i = 0; i < SZ(adj[u]); i ++){ int v = adj[u][i]; if(v == p) continue ; int x = id[u][v]; f[v] = f[u] + dp[u][((1 << 10) - 1) ^ (1 << x)]; update(v, u); } } void Dfs(int u, int p){ vector<int> upd; for(int v : adj[u]){ if(v == p) continue ; Dfs(v, u); int x = id[u][v]; dp[u][(1 << x)] = max(dp[u][(1 << x)], dp[v][(1 << 10) - 1]); } update(u, p); for(auto [a, b, c] : k[u]){ int x = edge[a][0]; int y = edge[a][1]; int w = edge[a][2]; int mask = 0; if(id[u][b] != -1) mask |= (1 << id[u][b]); if(id[u][c] != -1) mask |= (1 << id[u][c]); if(!dp[u][mask]) upd.push_back(mask); int val = w; if(x != u) val += f[x] + dp[x][(1 << 10) - 1]; if(y != u) val += f[y] + dp[y][(1 << 10) - 1]; dp[u][mask] = max(dp[u][mask], val); } for(int i = 0; i < 10; i ++){ int mask = 1 << i; upd.push_back(mask); } for(int mask = 0; mask < (1 << 10); mask ++){ for(int x : upd){ if((mask & x) == 0){ dp[u][mask | x] = max(dp[u][mask | x], dp[u][mask] + dp[u][x]); } } } } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m; int sum = 0; for(int i = 1; i <= m; i ++){ int u, v, w; cin >> u >> v >> w; if(!w){ adj[u].push_back(v); adj[v].push_back(u); } else { edge.push_back({u, v, w}); } sum += w; } memset(id, -1, sizeof(id)); dfs(1, 1); for(int i = 0; i < SZ(edge); i ++){ int u = edge[i][0]; int v = edge[i][1]; int p = get_LCA(u, v); int len = h[u] + h[v] - 2 * h[p]; u = jump(u, h[u] - h[p] - 1); v = jump(v, h[v] - h[p] - 1); if(len % 2 == 0){ k[p].push_back({i, u, v}); } } Dfs(1, 1); //for(int i = 1; i <= n; i ++) cout << dp[i][(1 << 10) - 1] << "\n"; cout << sum - dp[1][(1 << 10) - 1] << "\n"; // 3176 return 0; }

Compilation message (stderr)

training.cpp: In function 'void Dfs(int, int)':
training.cpp:92:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   92 |     for(auto [a, b, c] : k[u]){
      |              ^
#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...