oj.uz

Submission #969028

# Submission time Handle Problem Language Result Execution time Memory
969028 2024-04-24T11:50:41 Z Hugo1729 Race (IOI11_race) C++17
0 / 100
 3 ms 9972 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9564 KB Output is correct
2 Correct 3 ms 9564 KB Output is correct
3 Correct 2 ms 9564 KB Output is correct
4 Correct 2 ms 9564 KB Output is correct
5 Correct 3 ms 9972 KB Output is correct
6 Correct 2 ms 9564 KB Output is correct
7 Correct 2 ms 9564 KB Output is correct
8 Correct 2 ms 9564 KB Output is correct
9 Correct 2 ms 9564 KB Output is correct
10 Correct 2 ms 9564 KB Output is correct
11 Incorrect 2 ms 9564 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9564 KB Output is correct
2 Correct 3 ms 9564 KB Output is correct
3 Correct 2 ms 9564 KB Output is correct
4 Correct 2 ms 9564 KB Output is correct
5 Correct 3 ms 9972 KB Output is correct
6 Correct 2 ms 9564 KB Output is correct
7 Correct 2 ms 9564 KB Output is correct
8 Correct 2 ms 9564 KB Output is correct
9 Correct 2 ms 9564 KB Output is correct
10 Correct 2 ms 9564 KB Output is correct
11 Incorrect 2 ms 9564 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9564 KB Output is correct
2 Correct 3 ms 9564 KB Output is correct
3 Correct 2 ms 9564 KB Output is correct
4 Correct 2 ms 9564 KB Output is correct
5 Correct 3 ms 9972 KB Output is correct
6 Correct 2 ms 9564 KB Output is correct
7 Correct 2 ms 9564 KB Output is correct
8 Correct 2 ms 9564 KB Output is correct
9 Correct 2 ms 9564 KB Output is correct
10 Correct 2 ms 9564 KB Output is correct
11 Incorrect 2 ms 9564 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9564 KB Output is correct
2 Correct 3 ms 9564 KB Output is correct
3 Correct 2 ms 9564 KB Output is correct
4 Correct 2 ms 9564 KB Output is correct
5 Correct 3 ms 9972 KB Output is correct
6 Correct 2 ms 9564 KB Output is correct
7 Correct 2 ms 9564 KB Output is correct
8 Correct 2 ms 9564 KB Output is correct
9 Correct 2 ms 9564 KB Output is correct
10 Correct 2 ms 9564 KB Output is correct
11 Incorrect 2 ms 9564 KB Output isn't correct
12 Halted 0 ms 0 KB -