Submission #833066

#	Time	Username	Problem	Language	Result	Execution time	Memory
833066		idiotcomputer	Race (IOI11_race)	C++11	100 / 100	345 ms	102864 KiB

race

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

const int mxN = 2*1e5;

set<pair<long long int, int>> all[mxN];
int p[mxN];
long long int add[mxN];
long long int a2[mxN];

long long int res;
long long int k;

void upd(int c){
    while (p[c] != p[p[c]]){
        p[c] = p[p[c]];
    }
}

void comb(int a, int b){
    if (all[a].size() > all[b].size()){
        swap(a,b);
    }
    
    for (auto it = all[a].begin(); it != all[a].end(); it++){
        long long int val = (*it).first + add[a] - add[b];
        int nl = (*it).second + a2[a] - a2[b];
        long long int needed = k - val - 2*add[b];
        
        auto it2 = all[b].lower_bound({needed,-1 * 1e9});
        if ((it2 != all[b].end()) && ((*it2).first == needed)){
            res = min(res, nl + (*it2).second + 2 * a2[b]);
        }
        
       // all[b].insert({val,nl});
       // cout << "HERERE " << a << " "<<b<< ": " << val+add[b] << " " << nl + a2[b] <<'\n';
    }
    for (auto it = all[a].begin(); it != all[a].end(); it++){
        long long int val = (*it).first + add[a] - add[b];
        int nl = (*it).second + a2[a] - a2[b];
        all[b].insert({val,nl});
    }
    
    
    p[a] = b;
    
}

void dfs(int node, int parent, vector<vector<pair<int, long long int>>> &connect){
    p[node] = node;
    add[node] = 0;
    a2[node] = 0;
    all[node].clear();
    int next;
    for (int i =0; i < connect[node].size(); i++){
        next = connect[node][i].first;
        if (next == parent){
            continue;
        }
        dfs(next,node,connect);
        upd(node);
        upd(next);
        int a= p[node];
        int b = p[next];
        add[b] += connect[node][i].second;
        a2[b] += 1;
        auto it = all[b].lower_bound({k-add[b],-1*1e9});
        if ((it != all[b].end()) && ((*it).first == k-add[b])){
            res = min(res, (*it).second + a2[b]);
        }
        comb(a,b);
    }
    upd(node);
    all[p[node]].insert({-1*add[p[node]],-1*a2[p[node]]});
  /*  cout<< node << ":\n";
    for (auto it = all[p[node]].begin(); it != all[p[node]].end(); it++){
        cout << (*it).first+add[p[node]] << "," << (*it).second+a2[p[node]] << ' ';
    }
    cout << '\n';*/
}

int best_path(int n,int ck, int h[][2], int l[]){
    if (ck == 0){
        return 0;
    }
    vector<vector<pair<int,long long int>>> connect(n);
    k = ck;
    
    for (int i =0; i < n-1; i++){
        connect[h[i][0]].push_back({h[i][1],l[i]});
        connect[h[i][1]].push_back({h[i][0],l[i]});
    }
    
  /*  for (int i =0; i < n; i++){
        cout << i << ": ";
        for (int j = 0; j < connect[i].size();j++){
            cout<<connect[i][j].first<<","<<connect[i][j].second<<"  ";
        }
        cout<<'\n';
    }*/
    
    res = 1e9;
    dfs(0,-1,connect);
    if (res == 1e9){
        return -1;
    }
    return res;
}

Compilation message (stderr)

race.cpp: In function 'void dfs(int, int, std::vector<std::vector<std::pair<int, long long int> > >&)':
race.cpp:55:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for (int i =0; i < connect[node].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 57 / 57