Submission #477086

#	Time	Username	Problem	Language	Result	Execution time	Memory
477086		RambaXGorilla	Training (IOI07_training)	C++17	100 / 100	110 ms	16896 KiB

training

#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 (stderr)

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 / 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