Submission #386481

#TimeUsernameProblemLanguageResultExecution timeMemory
386481achibasadzishviliTraining (IOI07_training)C++17
82 / 100
658 ms6380 KiB
#include<bits/stdc++.h> #define ll int #define f first #define s second #define pb push_back #define mp make_pair using namespace std; ll P[1005][19],timer,in[5005],out[5005]; ll n,m,ran[5005],lvl[5005]; vector<ll>v[5005]; vector<pair<ll,pair<ll,ll> > >g[5005]; ll dp[1005][1400]; bool don[1005][1400]; void go(ll x,ll par){ P[x][0]=par; for (int i=1;i<=13;i++) P[x][i]=P[P[x][i-1]][i-1]; timer++; in[x]=timer; for(int i=0; i<v[x].size(); i++){ if(v[x][i] != par){ lvl[v[x][i]] = lvl[x] + 1; go(v[x][i] , x); } } timer++; out[x] = timer; } int lca(int a,int b) { if(lvl[a] > lvl[b])swap(a,b); if(in[a] <= in[b] && out[b] <= out[a])return a; for(int i=13;i>=0;i--) if(P[a][i]) if(!(in[P[a][i]] <= in[b] && out[b] <= out[P[a][i]])) a=P[a][i]; return P[a][0]; } ll solve(ll x,ll mask){ if(don[x][mask])return dp[x][mask]; don[x][mask] = 1; ll fi = 0,r = 0; for(int i=0; i<v[x].size(); i++){ ran[v[x][i]] = r; r++; if(mask & (1 << i))continue; solve(v[x][i] , 0); fi += dp[v[x][i]][0]; } dp[x][mask] = fi; for(int i=0; i<g[x].size(); i++){ ll a = g[x][i].f , b = g[x][i].s.f , c = g[x][i].s.s; ll pa = -1, pb = -1; for(int j=0; j<v[x].size(); j++){ if(in[v[x][j]] <= in[a] && out[v[x][j]] >= out[a]){ pa = j; } if(in[v[x][j]] <= in[b] && out[v[x][j]] >= out[b]){ pb = j; } } if(pa != -1 && (mask & (1 << pa)))continue; if(pb != -1 && (mask & (1 << pb)))continue; ll k = a,ne = mask; if(pa != -1)ne ^= (1 << pa); if(pb != -1)ne ^= (1 << pb); ll cur = solve(x , ne); if(k != x)cur += solve(k , 0); ll pre = k; while(k != x){ k = P[k][0]; if(k == x)break; cur += solve(k , (1 << ran[pre])); pre = k; } k = b; if(k != x)cur += solve(k , 0); pre = k; while(k != x){ k = P[k][0]; if(k == x)break; cur += solve(k , (1 << ran[pre])); pre = k; } dp[x][mask] = max(dp[x][mask] , cur + g[x][i].s.s); } return dp[x][mask]; } int main(){ ios::sync_with_stdio(false); cin >> n >> m; ll sum = 0; vector<pair<ll,pair<ll,ll> > >ed; for(int i=1; i<=m; i++){ ll x,y,z; cin >> x >> y >> z; sum += z; if(z == 0){ v[x].pb(y); v[y].pb(x); } else { ed.pb(mp(x , mp(y , z))); } } go(1 , 0); for(int i=1; i<=n; i++) v[i].clear(); for(int i=2; i<=n; i++){ v[P[i][0]].pb(i); } for(int i=0; i<ed.size(); i++){ ll x = ed[i].f , y = ed[i].s.f , z = ed[i].s.s; ll p = lca(x , y); if((lvl[x] + lvl[y] - 2 * lvl[p]) % 2 == 1)continue; g[p].pb(mp(x , mp(y , z))); } cout << sum - solve(1 , 0) << '\n'; return 0; }

Compilation message (stderr)

training.cpp: In function 'void go(int, int)':
training.cpp:20:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for(int i=0; i<v[x].size(); i++){
      |                  ~^~~~~~~~~~~~
training.cpp: In function 'int solve(int, int)':
training.cpp:42:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for(int i=0; i<v[x].size(); i++){
      |                  ~^~~~~~~~~~~~
training.cpp:50:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for(int i=0; i<g[x].size(); i++){
      |                  ~^~~~~~~~~~~~
training.cpp:53:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         for(int j=0; j<v[x].size(); j++){
      |                      ~^~~~~~~~~~~~
training.cpp:51:46: warning: unused variable 'c' [-Wunused-variable]
   51 |         ll a = g[x][i].f , b = g[x][i].s.f , c = g[x][i].s.s;
      |                                              ^
training.cpp: In function 'int main()':
training.cpp:114:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |     for(int i=0; i<ed.size(); i++){
      |                  ~^~~~~~~~~~
#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...