Submission #969028

#	Time	Username	Problem	Language	Result	Execution time	Memory
969028		Hugo1729	Race (IOI11_race)	C++17	0 / 100	3 ms	9972 KiB

race

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

vector<pair<int,int>> adj[200000];
bool marked[200000]={0};
int sz[200000];
int ans=300000,k=0;

int dfs_sizes(int v, int pV){
    sz[v]=1;
    for(auto [w,d] : adj[v]){
        if(w!=pV&&!marked[w]){
            sz[v]+=dfs_sizes(w,v);
        }
    }

    return sz[v];
}

int find_centroid(int v, int pV, int size){
    // cout << 'c' << v << ' ' << pV << ' ' << size << '\n';
    for(auto [w,d] : adj[v]){
        if(w!=pV&&!marked[w]&&sz[w]>size/2){
            return find_centroid(w,v,size);
        }
    }
    return v;
}

vector<pair<int,int>> dfs_path(int v, int pV){
    vector<pair<int,int>> sus;
    for(auto [w,d] : adj[v]){
        if(w!=pV&&!marked[w]){
            vector<pair<int,int>> path = dfs_path(w,v);

            for(int i=0;i<path.size();i++)sus.push_back({path[i].first+d,path[i].second+1});
        }
    }

    sus.push_back({0,0});

    return sus;
}

void centroid_decomposition(int v){
    int d=dfs_sizes(v,v);
    int c = find_centroid(v,v,d);

    // cout << v << ' ' << c << ' ' << d << '\n';

    // for(int i=0;i<11;i++)cout << sz[i] << ' ';
    // cout << '\n';

    marked[c]=1;
    vector<pair<int,int>> sus;
    map<int,int> m;
    m[0]=0;

    for(auto [w,d] : adj[c]){
        // cout << 'a' << c << ' ' << w <<'\n';
        if(!marked[w]){
            // cout << 'w' << c << '\n';
            vector<pair<int,int>> path = dfs_path(w,v);
            centroid_decomposition(w);
            // cout << 'w' << c << '\n';

            for(int i=0;i<path.size();i++){
                path[i].first+=d;
                path[i].second++;
                if(k-path[i].first>=0&&m.count(k-path[i].first)){
                    ans=min(ans,m[k-path[i].first]+path[i].second);
                }
            }

            for(int i=0;i<path.size();i++){
                if(m.count(path[i].first))m[path[i].first]=min(m[path[i].first],path[i].second);
                else m[path[i].first]=path[i].second;
                sus.push_back(path[i]);
            }
        }
    }

    // sus.push_back({0,0});

    // cout << "sus" << ' ' << c << ' ';
    // for(int i=0;i<sus.size();i++)cout << '{' << sus[i].first << ' ' << sus[i].second << '}';
    // cout << '\n';


}

int best_path(int N, int K, int H[][2], int L[]){
    for(int i=0;i<N-1;i++){
        adj[H[i][0]].push_back({H[i][1],L[i]});
        adj[H[i][1]].push_back({H[i][0],L[i]});
    }

    k=K;

    centroid_decomposition(0);

    if(ans==300000)return -1;
    else return ans;
}

Compilation message (stderr)

race.cpp: In function 'std::vector<std::pair<int, int> > dfs_path(int, int)':
race.cpp:37:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |             for(int i=0;i<path.size();i++)sus.push_back({path[i].first+d,path[i].second+1});
      |                         ~^~~~~~~~~~~~
race.cpp: In function 'void centroid_decomposition(int)':
race.cpp:68:26: 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<path.size();i++){
      |                         ~^~~~~~~~~~~~
race.cpp:76:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |             for(int i=0;i<path.size();i++){
      |                         ~^~~~~~~~~~~~

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