Submission #483459

#	Time	Username	Problem	Language	Result	Execution time	Memory
483459		nicolaalexandra	Training (IOI07_training)	C++14	10 / 100	8 ms	4748 KiB

training

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

vector <int> L[DIM];
long long dp[DIM][1050],best[DIM];

struct muchie{
    int x,y,cost;
};
vector <muchie> mch,v[DIM];

int level[DIM],fth[DIM],first[DIM],E[DIM*3],p[DIM*3];
pair <int,int> rmq[20][DIM*3];

int n,m,i,j,x,y,cost,k;

void dfs (int nod, int tata){

    fth[nod] = tata;
    level[nod] = 1 + level[tata];
    E[++k] = nod;
    first[nod] = k;

    for (auto vecin : L[nod])
        if (vecin != tata){
            dfs (vecin,nod);
            E[++k] = nod;
        }

}

int get_lca (int x, int y){
    int posx = first[x], posy = first[y];
    if (posx > posy)
        swap (posx,posy);
    int nr = p[posy-posx+1];
    pair <int,int> sol = min (rmq[nr][posx],rmq[nr][posy-(1<<nr)+1]);
    return E[sol.second];
}

int get_poz (int x, int y){
    for (int i=0;i<L[x].size();i++)
        if (L[x][i] == y)
            return i;
}

void dfs2 (int nod, int tata){

    int ok = 0;
    for (auto vecin : L[nod]){
        ok = 1;
        dfs2 (vecin,nod);
    }

    if (!ok){
        best[nod] = 0;
    } else {
        int sz = L[nod].size();
        int maxi = (1<<sz);

        for (int mask=0;mask<maxi;mask++)
            for (int bit=0;bit<sz;bit++){
                int vecin = L[nod][bit];
                if (mask & (1<<bit))
                    dp[nod][mask] += best[vecin];
            }

        for (auto it : v[nod]){  /// nod e lca
            int x = it.x, y = it.y, cost = it.cost;

            if (x != nod && y != nod){
                long long sum = best[x] + best[y] + cost;
                int val = x;
                while (fth[val] != nod){

                    //int poz = get_poz (fth[val],val);
                    //sum += dp[fth[val]][( (1<<L[fth[val]].size()) - 1 ) ^ (1<<poz)];

                    for (auto it : L[fth[val]]){
                        if (it != val)
                            sum += best[it];
                    }

                    val = fth[val];
                }
                int pozx = get_poz (nod,val);

                val = y;
                while (fth[val] != nod){

                    for (auto it : L[fth[val]]){
                        if (it != val)
                            sum += best[it];
                    }

                    val = fth[val];
                }

                int pozy = get_poz (nod,val);

                sum += dp[nod][((1<<L[nod].size()) - 1) ^ (1<<pozx) ^ (1<<pozy) ];


                for (int mask=maxi-1;mask>=0;mask--){
                    if ( !((mask & (1<<pozx)) && (mask & (1<<pozy)) ))
                        continue;

                    dp[nod][mask] = max (dp[nod][mask],dp[nod][mask^(1<<pozx)^(1<<pozy)] + sum);
                }

            } else { /// am un singur lant

                int val = (x != nod) ? (x) : (y);

                long long sum = best[val] + cost;
                while (fth[val] != nod){

                    for (auto it : L[fth[val]]){
                        if (it != val)
                            sum += best[it];
                    }

                    val = fth[val];
                }

                int poz = get_poz (nod,val);

                sum += dp[nod][((1<<L[nod].size()) - 1) ^ (1<<poz)];

                for (int mask=maxi-1;mask>=0;mask--){
                    if (!(mask & (1<<poz)))
                        continue;
                    dp[nod][mask] = max (dp[nod][mask], dp[nod][mask^(1<<poz)] + sum);
                }

            }

        }


        for (int mask=0;mask<maxi;mask++)
            best[nod] = max (best[nod],dp[nod][mask]);
    }
}

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>m;
    for (i=1;i<=m;i++){
        cin>>x>>y>>cost;
        if (!cost){
            L[x].push_back(y);
            L[y].push_back(x);
        } else mch.push_back({x,y,cost});
    }

    dfs (1,0);

    for (i=2;i<=n;i++){
        for (j=0;j<L[i].size();j++)
            if (L[i][j] == fth[i])
                break;
        swap (L[i][j],L[i].back());
        L[i].pop_back();
    }

    for (i=1;i<=k;i++)
        rmq[0][i] = make_pair(level[E[i]],i);

    for (i=1;(1<<i)<=k;i++)
        for (j=1;j<=k;j++){
            rmq[i][j] = rmq[i-1][j];
            if (j + (1<<(i-1)) <= k && rmq[i-1][j + (1<<i-1)].first < rmq[i][j].first)
                rmq[i][j] = rmq[i-1][j + (1<<i-1)];
        }

    for (i=2;i<=k;i++)
        p[i] = p[i/2] + 1;


    long long total = 0;
    for (auto it : mch){
        int x = it.x, y = it.y;
        if (level[x] > level[y])
            swap (x,y);

        total += it.cost;

        if ( (level[y] - level[x]) % 2 )
            continue;

        int lca = get_lca (x,y);
        v[lca].push_back({x,y,it.cost});
    }

    dfs2 (1,0);

    cout<<total - best[1];

    return 0;
}

Compilation message (stderr)

training.cpp: In function 'int get_poz(int, int)':
training.cpp:43:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for (int i=0;i<L[x].size();i++)
      |                  ~^~~~~~~~~~~~
training.cpp: In function 'int main()':
training.cpp:164:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  164 |         for (j=0;j<L[i].size();j++)
      |                  ~^~~~~~~~~~~~
training.cpp:177:58: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  177 |             if (j + (1<<(i-1)) <= k && rmq[i-1][j + (1<<i-1)].first < rmq[i][j].first)
      |                                                         ~^~
training.cpp:178:47: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  178 |                 rmq[i][j] = rmq[i-1][j + (1<<i-1)];
      |                                              ~^~
training.cpp: In function 'int get_poz(int, int)':
training.cpp:46:1: warning: control reaches end of non-void function [-Wreturn-type]
   46 | }
      | ^

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