Submission #446657

#	Time	Username	Problem	Language	Result	Execution time	Memory
446657		Giselus	Race (IOI11_race)	C++14	100 / 100	1890 ms	59616 KiB

race

#include<cstdio>
#include<algorithm>
#include<vector>
#include<map>
#define S 200007

using namespace std;

vector < pair < int , int > > V[S];
int roz[S];
bool deleted[S];

void DFS(int x, int r){
    roz[x] = 1;
    for(int i = 0 ; i < V[x].size();i++){
        if(V[x][i].first != r && !deleted[V[x][i].first]){
            DFS(V[x][i].first,x);
            roz[x] += roz[V[x][i].first];
        }
    }
}

int Find(int x){
    for(int i = 0 ; i < V[x].size();i++){
        if(!deleted[V[x][i].first]){
            if(roz[V[x][i].first] > roz[x]/2){
                roz[x] -= roz[V[x][i].first];
                roz[V[x][i].first] += roz[x];
                return Find(V[x][i].first);
            }
        }
    }
    return x;
}

long long dp[S];
int l = 0;
int L[S];
int R[S];
int ID[S];
int poz[S];

void DFS2(int x, int r){
    L[x] = ++l;
    ID[l] = x;
    for(int i = 0 ; i < V[x].size();i++){
        int v = V[x][i].first;
        int c = V[x][i].second;
        if(v != r && !deleted[v]){
            poz[v] = poz[x] + 1;
            dp[v] = dp[x] + c;
            DFS2(v,x);
        }
    }
    R[x] = l;
}
long long k;
int odp = 1e9;
map < long long , int > mapa;

void decomposition(int x){
    DFS(x,x);
    int centroid = Find(x);
    poz[centroid] = 0;
    dp[centroid] = 0;
    DFS2(centroid,centroid);
    deleted[centroid] = 1;
    for(int i = 0 ; i < V[centroid].size();i++){
        int v = V[centroid][i].first;
        if(!deleted[v]){
            //printf("%d %d %d %d*\n",centroid,v,L[v],R[v]);
            for(int j = L[v]; j <= R[v];j++){
                int v2 = ID[j];
                if(dp[v2] == k){
                    odp = min(odp,poz[v2]);
                    //printf("%d %d$\n",centroid,v2);
                }
                if(mapa[k-dp[v2]]){
                    odp = min(odp, poz[v2] + mapa[k-dp[v2]]);
                    //printf("%d %d$$\n",centroid,v2);
                }
            }
            for(int j = L[v]; j <= R[v];j++){
                int v2 = ID[j];
                if(!mapa[dp[v2]]){
                    mapa[dp[v2]] = poz[v2];
                }else{
                    mapa[dp[v2]] = min(mapa[dp[v2]],poz[v2]);
                }
            }
        }
    }
    l = 0;
    mapa.clear();
    for(int i = 0 ; i < V[centroid].size();i++){
        int v = V[centroid][i].first;
        if(!deleted[v])
            decomposition(v);
    }
}

int best_path(int n, int _k, int H[][2], int L[]){
    k = _k;
    for(int i = 0 ; i < n-1;i++){
        V[H[i][0]+1].push_back({H[i][1]+1,L[i]});
        V[H[i][1]+1].push_back({H[i][0]+1,L[i]});
    }
    decomposition(1);
    if(odp < 1e8)
        return odp;
    return -1;
}

/*
int main(void){
    int A[10][2] = { {0,1}, {0,2}, {2,3}, {3,4}, {4,5}, {0,6}, {6,7}, {6,8}, {8,9}, {8,10}  };
    int B[10] = {3,4,5,4,6,3,2,5,6,7};
    printf("%d",best_path(11,12,A,B));
    return 0;
}
*/

Compilation message (stderr)

race.cpp: In function 'void DFS(int, int)':
race.cpp:15:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     for(int i = 0 ; i < V[x].size();i++){
      |                     ~~^~~~~~~~~~~~~
race.cpp: In function 'int Find(int)':
race.cpp:24:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(int i = 0 ; i < V[x].size();i++){
      |                     ~~^~~~~~~~~~~~~
race.cpp: In function 'void DFS2(int, int)':
race.cpp:46:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for(int i = 0 ; i < V[x].size();i++){
      |                     ~~^~~~~~~~~~~~~
race.cpp: In function 'void decomposition(int)':
race.cpp:68:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for(int i = 0 ; i < V[centroid].size();i++){
      |                     ~~^~~~~~~~~~~~~~~~~~~~
race.cpp:95:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |     for(int i = 0 ; i < V[centroid].size();i++){
      |                     ~~^~~~~~~~~~~~~~~~~~~~

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