Submission #386500

#	Time	Username	Problem	Language	Result	Execution time	Memory
386500		achibasadzishvili	Training (IOI07_training)	C++17	100 / 100	58 ms	10732 KiB

training

#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],t[1405][5005];
vector<ll>v[5005];
vector<pair<ll,pair<ll,ll> > >g[5005];
ll dp[1005][1400];
bool don[1005][1400],tu[1405][5005];
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 ad = solve(x , ne),cur = 0;
        if(tu[x][i]){
            dp[x][mask] = max(dp[x][mask] , ad + t[x][i]);
            continue;
        }
        tu[x][i] = 1;
        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;
        }
        cur += g[x][i].s.s;
        t[x][i] = cur;
        dp[x][mask] = max(dp[x][mask] , ad + cur);
    }
    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:121: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]
  121 |     for(int i=0; i<ed.size(); i++){
      |                  ~^~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 7 / 7
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 9 / 9
• Subtask 8: 9 / 9
• Subtask 9: 9 / 9
• Subtask 10: 9 / 9
• Subtask 11: 9 / 9