Submission #753688

#TimeUsernameProblemLanguageResultExecution timeMemory
753688lukameladzeTraining (IOI07_training)C++14
100 / 100
18 ms8392 KiB
# include <bits/stdc++.h> using namespace std; #define f first #define s second #define pii pair <int, int> #define pb push_back const int N = 1005, M = 5005; int t,n,m,a[N],in[N],out[N],tin, dp[N][1025],id[N][N]; int par[N],lv[N]; vector <int> v[N]; void dfs(int a, int p) { in[a] = ++tin; par[a] = p; lv[a] = lv[p] + 1; for (int to : v[a]) { if (to == p) continue; dfs(to, a); } out[a] = tin; } int upper(int a, int b) { return (in[a] <= in[b] && out[a] >= out[b]); } int lca(int a, int b) { int cur = a; while (!upper(cur, b)) { cur = par[cur]; } return cur; } int get(int a, int p) { int cur = a, lst = -1, ans = 0; while (cur != p) { if (lst == -1) ans += dp[cur][0]; else ans += dp[cur][(1<<id[cur][lst])]; lst = cur; cur = par[cur]; } return ans; } vector <array <int, 3> > g[N]; int kth(int x, int k) { while (k--) { x = par[x]; } return x; } void dfs1(int a, int p) { int cnt = 0; for (int to : v[a]) { if (to == p) continue; id[a][to] = cnt; cnt++; dfs1(to, a); } vector <array <int, 4> > pot; for (array <int, 3> edge : g[a]) { int x = edge[0], y = edge[1], z = edge[2]; int msk = 0; if (a != x) { int getx = kth(x, lv[x] - lv[a] - 1); msk |= (1<<id[a][getx]); } if (a != y) { int gety = kth(y, lv[y] - lv[a] - 1); msk |= (1<<id[a][gety]); } pot.pb({x, y, z, msk}); } for (int msk = 0; msk < (1<<cnt); msk++) { for (int to : v[a]){ if (to == p) continue; if (!((1<<id[a][to])&msk)) dp[a][msk] += dp[to][0]; } } for (array <int, 4> edge : pot) { int x = edge[0], y = edge[1], z = edge[2], cur_mask = edge[3]; int to_add = get(x, a) + get(y, a) + z; for (int msk = (1<<cnt) - 1; msk >= 0; msk--) { if ((msk & cur_mask)) continue; int cur_pas = dp[a][msk | cur_mask]; // add(x -- y) wibo cur_pas += to_add; dp[a][msk] = max(dp[a][msk], cur_pas); } //cout<<a<<" "<<dp[a][0]<<" "<<dp[a][1]<<"\n"; } } main() { std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0); cin>>n>>m; vector < array <int, 3 > > vec, vn; int sum = 0; for (int i = 1; i <= m; i++) { int a, b, c; cin>>a>>b>>c; sum += c; if (c == 0) { v[a].pb(b); v[b].pb(a); } else { vec.pb({a, b, c}); } } dfs(1, 0); for (array <int, 3> x : vec) { int a = x[0], b = x[1], c = x[2]; int dist = lv[a] + lv[b] - 2 * lv[lca(a, b)]; if (dist % 2 == 1) { } else vn.pb(x); } vec = vn; for (array <int, 3> x : vec) { int a = x[0], b = x[1], c = x[2]; g[lca(a, b)].pb({a,b,c}); } dfs1(1, 0); cout<<sum - dp[1][0]<<"\n"; }

Compilation message (stderr)

training.cpp:91:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   91 | main() {
      | ^~~~
training.cpp: In function 'int main()':
training.cpp:109:27: warning: unused variable 'c' [-Wunused-variable]
  109 |   int a = x[0], b = x[1], c = x[2];
      |                           ^
#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...