Submission #411303

#	Time	Username	Problem	Language	Result	Execution time	Memory
411303		couplefire	Training (IOI07_training)	C++17	100 / 100	65 ms	10956 KiB

training

#include<bits/stdc++.h>
using namespace std;

long long P[1005][19],timer,in[5005],out[5005];
long long n,m,ran[5005],lvl[5005],t[1405][5005];
vector<long long>v[5005];
vector<pair<long long,pair<long long,long long> > >g[5005];
long long dp[1005][1400];
bool don[1005][1400],tu[1405][5005];

void go(long long x,long long 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];
}
long long solve(long long x,long long mask){
    if(don[x][mask])return dp[x][mask];
    don[x][mask] = 1;
    long long 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++){
        long long a = g[x][i].first , b = g[x][i].second.first , c = g[x][i].second.second;
        long long pa = -1, push_back = -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]){
                push_back = j;
            }
        }
        if(pa != -1 && (mask & (1 << pa)))continue;
        if(push_back != -1 && (mask & (1 << push_back)))continue;
        long long k = a,ne = mask;
        if(pa != -1)ne ^= (1 << pa);
        if(push_back != -1)ne ^= (1 << push_back);
        long long 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);
        long long 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].second.second;
        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;
    long long sum = 0;
    vector<pair<long long,pair<long long,long long> > >ed;
    for(int i=1; i<=m; i++){
        long long x,y,z;
        cin >> x >> y >> z;
        sum += z;
        if(z == 0){
            v[x].push_back(y);
            v[y].push_back(x);
        }
        else {
            ed.push_back(make_pair(x , make_pair(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]].push_back(i);
    }
    for(int i=0; i<ed.size(); i++){
        long long x = ed[i].first , y = ed[i].second.first , z = ed[i].second.second;
        long long p = lca(x , y);
        if((lvl[x] + lvl[y] - 2 * lvl[p]) % 2 == 1)continue;
        g[p].push_back(make_pair(x , make_pair(y , z)));
    }
    cout << sum - solve(1 , 0) << '\n';
}

Compilation message (stderr)

training.cpp: In function 'void go(long long int, long long int)':
training.cpp:17:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for(int i=0; i<v[x].size(); i++){
      |                  ~^~~~~~~~~~~~
training.cpp: In function 'long long int solve(long long int, long long int)':
training.cpp:39:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for(int i=0; i<v[x].size(); i++){
      |                  ~^~~~~~~~~~~~
training.cpp:47:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for(int i=0; i<g[x].size(); i++){
      |                  ~^~~~~~~~~~~~
training.cpp:50:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         for(int j=0; j<v[x].size(); j++){
      |                      ~^~~~~~~~~~~~
training.cpp:48:66: warning: unused variable 'c' [-Wunused-variable]
   48 |         long long a = g[x][i].first , b = g[x][i].second.first , c = g[x][i].second.second;
      |                                                                  ^
training.cpp: In function 'int main()':
training.cpp:115:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |     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