oj.uz

Submission #477086

# Submission time Handle Problem Language Result Execution time Memory
477086 2021-09-30T06:46:00 Z RambaXGorilla Training (IOI07_training) C++17
100 / 100
 110 ms 16896 KB 
#include<cstdio>
#include<algorithm>
#include<utility>
#include<vector>
using namespace std;
typedef pair <int,int> ii;
typedef pair <ii,int> iii;
int N, M;
int roads[5010][4];
int sum = 0;
vector <int> tree[1010];
int pows[20];
int cons[1010];
int ends[1010];
int cnt = 0;
int depths[1010];
int ancs[1010][20];
vector <iii> tops[1010];
int maxCosts[1010][1010];
int locs[1010];
vector <int> combs[1030];
vector <int> children;
int binToDec(vector <int> bin){
    int dec = 0;
    for(int i = 0;i < bin.size();i++){
        dec += bin[i] << i;
    }
    return dec;
}
void renumCities(int city){
    cnt += 1;
    cons[city] = cnt;
    for(int i = 0;i < tree[city].size();i++){
        int next = tree[city][i];
        if(cons[next] == -1){
            renumCities(next);
        }
    }
    ends[cons[city]] = cnt;
}
void getVals(int city){
    for(int i = 0;i < tree[city].size();i++){
        int next = tree[city][i];
        depths[next] = depths[city] + 1;
        ancs[next][0] = city;
        getVals(next);
    }
}
int calcCombs(vector <int> select, int index, int city){
    if(index == tops[city].size()){
        int branchsum1 = 0;
        for(int i = 0;i < select.size();i++){
            if(!select[i]){
                branchsum1 += maxCosts[tree[city][i]][0];
            }
        }
        return branchsum1;
    }
    int selectNum = binToDec(select);
    if(combs[selectNum][index] != -1){
        return combs[selectNum][index];
    }
    combs[selectNum][index] = calcCombs(select, index + 1, city);
    iii cur = tops[city][index];
    int node1 = cur.first.first;
    int node2 = cur.first.second;
    int loc1 = locs[node1];
    int loc2 = locs[node2];
    int branchsum2 = maxCosts[tree[city][loc1]][node1];
    if(node1 != node2){
        branchsum2 += maxCosts[tree[city][loc2]][node2];
    }
    if(!select[loc1] && !select[loc2]){
        select[loc1] = 1;
        select[loc2] = 1;
        combs[selectNum][index] = max(combs[selectNum][index], calcCombs(select, index + 1, city) + cur.second + branchsum2);
    }
    return combs[selectNum][index];
}
void calcMaxCosts(int city, vector <int> paths){
    if(tree[city].empty()){
        maxCosts[city][0] = 0;
        maxCosts[city][city] = 0;
        return;
    }
    if(!paths.empty() && paths[0] == city){
        paths.erase(paths.begin());
    }
    int nodups[1010] = {};
    for(int i = 0;i < paths.size();i++){
        nodups[paths[i]] = 1;
    }
    for(int i = 0;i < tops[city].size();i++){
        nodups[tops[city][i].first.first] = 1;
        nodups[tops[city][i].first.second] = 1;
    }
    vector <int> subpaths[max((int) tree[city].size(), 1)];
    for(int i = 0;i < 1010;i++){
        if(nodups[i]){
            subpaths[upper_bound(tree[city].begin(), tree[city].end(), i) - tree[city].begin() - 1].push_back(i);
        }
    }
    for(int i = 0;i < tree[city].size();i++){
        calcMaxCosts(tree[city][i], subpaths[i]);
    }
    for(int i = 0;i < tree[city].size();i++){
        for(int j = 0;j < subpaths[i].size();j++){
            locs[subpaths[i][j]] = i;
        }
    }
    for(int i = 0;i < 1030;i++){
        combs[i] = vector <int> (tops[city].size(), -1);
    }
    children = vector <int> (tree[city].size(), 0);
    maxCosts[city][0] = calcCombs(children, 0, city);
    maxCosts[city][city] = maxCosts[city][0];
    for(int i = 0;i < paths.size();i++){
        children[locs[paths[i]]] = 1;
        maxCosts[city][paths[i]] = calcCombs(children, 0, city) + maxCosts[tree[city][locs[paths[i]]]][paths[i]];
        children[locs[paths[i]]] = 0;
    }
}
int main(){
    scanf("%d%d",&N,&M);
    for(int i = 0;i < M;i++){
        scanf("%d%d%d",&roads[i][0],&roads[i][1],&roads[i][2]);
        sum += roads[i][2];
        if(roads[i][2] == 0){
            tree[roads[i][0]].push_back(roads[i][1]);
            tree[roads[i][1]].push_back(roads[i][0]);
        }
    }
    int length = 1;
    for(int i = 0;i < 20;i++){
        pows[i] = length;
        length *= 2;
    }
    for(int i = 0;i < 1010;i++){
        cons[i] = -1;
    }
    renumCities(1);
    for(int i = 0;i < 1010;i++){
        tree[i].clear();
    }
    for(int i = 0;i < M;i++){
        if(roads[i][2] == 0){
            tree[min(cons[roads[i][0]], cons[roads[i][1]])].push_back(max(cons[roads[i][0]], cons[roads[i][1]]));
        }
    }
    depths[1] = 0;
    getVals(1);
    for(int j = 1;j < 20;j++){
        for(int i = 1;i < N + 1;i++){
            if(depths[i] - pows[j] < 0){
                continue;
            }
            ancs[i][j] = ancs[ancs[i][j - 1]][j - 1];
        }
    }
    for(int i = 0;i < M;i++){
        if(roads[i][2] == 0){
            continue;
        }
        int u = cons[roads[i][0]];
        int v = cons[roads[i][1]];
        int c = roads[i][2];
        if(depths[u] > depths[v]){
            swap(u, v);
        }
        int uT = u;
        int vT = v;
        int uC = u;
        int vC = v;
        int d = depths[v] - depths[u];
        int lca;
        for(int j = 19;j > -1;j--){
            if(pows[j] <= d){
                vT = ancs[vT][j];
                d -= pows[j];
            }
        }
        if(uT == vT){
            lca = uT;
            u = v;
            goto gotLCA;
        }
        for(int j = 19;j > -1;j--){
            if(ancs[uT][j] != ancs[vT][j]){
                uT = ancs[uT][j];
                vT = ancs[vT][j];
            }
        }
        lca = ancs[uT][0];
        gotLCA:
        if((depths[uC] + depths[vC] - depths[lca] * 2) % 2 == 1){
            continue;
        }
        tops[lca].push_back(iii(ii(u, v), c));
    }
    calcMaxCosts(1, vector <int> ());
    printf("%d",sum - maxCosts[1][0]);
}

Compilation message

training.cpp: In function 'int binToDec(std::vector<int>)':
training.cpp:25:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for(int i = 0;i < bin.size();i++){
      |                   ~~^~~~~~~~~~~~
training.cpp: In function 'void renumCities(int)':
training.cpp:33:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for(int i = 0;i < tree[city].size();i++){
      |                   ~~^~~~~~~~~~~~~~~~~~~
training.cpp: In function 'void getVals(int)':
training.cpp:42:21: 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 < tree[city].size();i++){
      |                   ~~^~~~~~~~~~~~~~~~~~~
training.cpp: In function 'int calcCombs(std::vector<int>, int, int)':
training.cpp:50:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     if(index == tops[city].size()){
      |        ~~~~~~^~~~~~~~~~~~~~~~~~~~
training.cpp:52:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |         for(int i = 0;i < select.size();i++){
      |                       ~~^~~~~~~~~~~~~~~
training.cpp: In function 'void calcMaxCosts(int, std::vector<int>)':
training.cpp:90:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |     for(int i = 0;i < paths.size();i++){
      |                   ~~^~~~~~~~~~~~~~
training.cpp:93:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |     for(int i = 0;i < tops[city].size();i++){
      |                   ~~^~~~~~~~~~~~~~~~~~~
training.cpp:103:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |     for(int i = 0;i < tree[city].size();i++){
      |                   ~~^~~~~~~~~~~~~~~~~~~
training.cpp:106:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |     for(int i = 0;i < tree[city].size();i++){
      |                   ~~^~~~~~~~~~~~~~~~~~~
training.cpp:107:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |         for(int j = 0;j < subpaths[i].size();j++){
      |                       ~~^~~~~~~~~~~~~~~~~~~~
training.cpp:117:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |     for(int i = 0;i < paths.size();i++){
      |                   ~~^~~~~~~~~~~~~~
training.cpp: In function 'int main()':
training.cpp:124:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |     scanf("%d%d",&N,&M);
      |     ~~~~~^~~~~~~~~~~~~~
training.cpp:126:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |         scanf("%d%d%d",&roads[i][0],&roads[i][1],&roads[i][2]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 9412 KB Output is correct
2 Correct 46 ms 10692 KB Output is correct

Subtask #4
7.0 / 7.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
9.0 / 9.0

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

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2048 KB Output is correct
2 Correct 5 ms 2508 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 4044 KB Output is correct
2 Correct 9 ms 3764 KB Output is correct
3 Correct 65 ms 6860 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 6392 KB Output is correct
2 Correct 75 ms 9384 KB Output is correct
3 Correct 24 ms 6980 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 5060 KB Output is correct
2 Correct 15 ms 4720 KB Output is correct
3 Correct 41 ms 16896 KB Output is correct
4 Correct 14 ms 6500 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 13384 KB Output is correct
2 Correct 110 ms 13016 KB Output is correct
3 Correct 23 ms 10328 KB Output is correct
4 Correct 61 ms 7824 KB Output is correct