Submission #446655

#	Time	Username	Problem	Language	Result	Execution time	Memory
446655		Giselus	Race (IOI11_race)	C++14	0 / 100	41 ms	12612 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 poz[S];

void DFS2(int x, int r){
    L[x] = ++l;
    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);
    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++){
                if(dp[j] == k)
                    odp = min(odp,poz[j]);
                if(mapa[k-dp[j]]){
                    odp = min(odp, poz[j] + mapa[k-dp[j]]);
                }
            }
            for(int j = L[v]; j <= R[v];j++){
                if(!mapa[dp[j]]){
                    mapa[dp[j]] = poz[j];
                }else{
                    mapa[dp[j]] = min(mapa[dp[j]],poz[j]);
                }
            }
        }
    }
    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;
}

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:44: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]
   44 |     for(int i = 0 ; i < V[x].size();i++){
      |                     ~~^~~~~~~~~~~~~
race.cpp: In function 'void decomposition(int)':
race.cpp:63: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]
   63 |     for(int i = 0 ; i < V[centroid].size();i++){
      |                     ~~^~~~~~~~~~~~~~~~~~~~
race.cpp:83: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]
   83 |     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