oj.uz

Submission #483466

# Submission time Handle Problem Language Result Execution time Memory
483466 2021-10-29T17:21:01 Z nicolaalexandra Training (IOI07_training) C++14
100 / 100
 13 ms 4812 KB 
#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];
vector <pair<int,int> > w;
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){


    for (auto vecin : L[nod])
        dfs2 (vecin,nod);


    int sz = L[nod].size();

    if (!sz)
        return;

    int maxi = (1<<sz);

    w.clear(); /// toate starile din care pot sa actualizez dinamica

    for (int bit=0;bit<sz;bit++){
        int vecin = L[nod][bit];
        w.push_back(make_pair( (1<<bit), 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, mask = 0;
            while (fth[val] != nod){

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

                val = fth[val];
            }
            int pozx = get_poz (nod,val);
            mask |= (1<<pozx);

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


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

                val = fth[val];
            }

            int pozy = get_poz (nod,val);
            mask |= (1<<pozy);

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


            w.push_back(make_pair(mask,sum));

           

        } else { /// am un singur lant

            int val = (x != nod) ? (x) : (y);
            int mask = 0;
            long long sum = best[val] + cost;

            while (fth[val] != nod){

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

                val = fth[val];
            }

            int poz = get_poz (nod,val);
            mask |= (1<<poz);

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

            w.push_back(make_pair(mask,sum));
        
        }

    }

    for (int mask=0;mask<maxi;mask++){
        for (auto it : w)
            if ( (it.first & mask) == it.first)
                dp[nod][mask] = max (dp[nod][mask],dp[nod][mask^it.first] + it.second);
    }

    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

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:160:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  160 |         for (j=0;j<L[i].size();j++)
      |                  ~^~~~~~~~~~~~
training.cpp:173:58: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  173 |             if (j + (1<<(i-1)) <= k && rmq[i-1][j + (1<<i-1)].first < rmq[i][j].first)
      |                                                         ~^~
training.cpp:174:47: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  174 |                 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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 588 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 4684 KB Output is correct
2 Correct 6 ms 4812 KB Output is correct

Subtask #4
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 460 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 588 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 844 KB Output is correct
2 Correct 1 ms 844 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1100 KB Output is correct
2 Correct 3 ms 972 KB Output is correct
3 Correct 6 ms 1648 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2252 KB Output is correct
2 Correct 9 ms 1612 KB Output is correct
3 Correct 5 ms 1784 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 972 KB Output is correct
2 Correct 3 ms 1740 KB Output is correct
3 Correct 13 ms 4804 KB Output is correct
4 Correct 4 ms 1868 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2252 KB Output is correct
2 Correct 13 ms 4724 KB Output is correct
3 Correct 9 ms 2124 KB Output is correct
4 Correct 8 ms 1740 KB Output is correct