Submission #446656

#	Time	Username	Problem	Language	Result	Execution time	Memory
446656		Giselus	Race (IOI11_race)	C++14	0 / 100	3 ms	4940 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);
    DFS2(centroid,centroid);
    deleted[centroid] = 1;
    for(int i = 0 ; i < V[centroid].size();i++){
        int v = V[centroid][i].first;
        if(!deleted[v]){
            for(int j = L[v]; j <= R[v];j++){
                int v2 = ID[j];
                if(dp[v2] == k)
                    odp = min(odp,poz[v2]);
                if(mapa[k-dp[v2]]){
                    odp = min(odp, poz[v2] + mapa[k-dp[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);
    return odp;
}
/*
int main(void){
    int A[3][2] = {{0,1}, {1,2}, {1,3}};
    int B[3] = {1,2,4};
    printf("%d",best_path(4,3,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:66: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]
   66 |     for(int i = 0 ; i < V[centroid].size();i++){
      |                     ~~^~~~~~~~~~~~~~~~~~~~
race.cpp:89: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]
   89 |     for(int i = 0 ; i < V[centroid].size();i++){
      |                     ~~^~~~~~~~~~~~~~~~~~~~

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