oj.uz

Submission #898207

# Submission time Handle Problem Language Result Execution time Memory
898207 2024-01-04T11:32:57 Z ThylOne Race (IOI11_race) C++14
9 / 100
 2092 ms 262144 KB 
#include "race.h"
#include<bits/stdc++.h>
using namespace std;
const int maxiN = 200000;
#define edge pair<int,int>
#define fils first
#define weight second

vector<edge> links[maxiN];
vector<bool> blocked;
int nbNode;
int target;
int ANS = maxiN*2;
vector<pair<int,int>>  solve(int node,int W=0){
  //1 - trouver la centroid
  vector<int> nodes;
  map<int,int> deg;
  std::function<int(int, int)> dfs = [&](int node_,int papa=-1){
    if(blocked[node_])return 0;
    nodes.push_back(node_);
    for(auto e:links[node_])if(papa!=e.fils){
      int re = dfs(e.fils,node_);
      deg[node_]+=re;
    }
    
    return 1;
  };
  dfs(node,-1);
  int centroid=node;
  int maxiDeg = deg[node];
  for(int node_:nodes){
    if(maxiDeg<deg[node_]){
      deg[node_]=maxiDeg;
      centroid=node_;
    }
  }
  blocked[centroid]=true;
  
  //2 Divide
  vector<vector<pair<int,int>>> maps;
  for(auto e:links[centroid])if(!blocked[e.first]){
    vector<pair<int,int>> re = solve(e.fils,e.weight);
    maps.push_back(re);
  }

  map<int,int> VAL;
  VAL[0]=0;
  vector<pair<int,int>> returnPairs;
  for(int i = 0;i<maps.size();i++){

    for(auto key:maps[i]){
      if(VAL.count(target-key.first)){
        ANS = min(ANS,key.second+VAL[target-key.first]);
      }
      
      returnPairs.push_back({key.first+W,key.second+1});
    }
    //ajouter la valeur dans la map
    for(auto key:maps[i]){
      if(VAL.count(key.first)){
        VAL[key.first] = min(VAL[key.first],key.second);
      }else{
        VAL[key.first] = key.second;
      }
    }
  }
  //3 Conquer

  //On en profite pour remplir le vecteur de fin
  
  
  //cout<<centroid<<' '<<ANS<<endl; 
  //On oublit pas la ptit nouvelle
  
  returnPairs.push_back({W,1});
  return returnPairs;
}
int best_path(int N, int K, int H[][2], int L[])
{
  target=K;
  nbNode=N;
  
  blocked.resize(N,false);
  fill(blocked.begin(),blocked.end(),false);
  for(int i = 0;i<N-1;i++){
    links[H[i][0]].push_back({H[i][1],L[i]});
    links[H[i][1]].push_back({H[i][0],L[i]});
  }
  
  solve(0);
  
  return (ANS==2*maxiN?-1:ANS);
}

Compilation message

race.cpp: In function 'std::vector<std::pair<int, int> > solve(int, int)':
race.cpp:49:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   for(int i = 0;i<maps.size();i++){
      |                 ~^~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9048 KB Output is correct
2 Correct 3 ms 9052 KB Output is correct
3 Correct 2 ms 9052 KB Output is correct
4 Correct 2 ms 9052 KB Output is correct
5 Correct 2 ms 9052 KB Output is correct
6 Correct 2 ms 8892 KB Output is correct
7 Correct 2 ms 8888 KB Output is correct
8 Correct 2 ms 9052 KB Output is correct
9 Correct 2 ms 9052 KB Output is correct
10 Correct 3 ms 9052 KB Output is correct
11 Correct 2 ms 9052 KB Output is correct
12 Correct 2 ms 9052 KB Output is correct
13 Correct 2 ms 9052 KB Output is correct
14 Correct 2 ms 9052 KB Output is correct
15 Correct 2 ms 9052 KB Output is correct
16 Correct 2 ms 9052 KB Output is correct
17 Correct 2 ms 9052 KB Output is correct
18 Correct 2 ms 9052 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9048 KB Output is correct
2 Correct 3 ms 9052 KB Output is correct
3 Correct 2 ms 9052 KB Output is correct
4 Correct 2 ms 9052 KB Output is correct
5 Correct 2 ms 9052 KB Output is correct
6 Correct 2 ms 8892 KB Output is correct
7 Correct 2 ms 8888 KB Output is correct
8 Correct 2 ms 9052 KB Output is correct
9 Correct 2 ms 9052 KB Output is correct
10 Correct 3 ms 9052 KB Output is correct
11 Correct 2 ms 9052 KB Output is correct
12 Correct 2 ms 9052 KB Output is correct
13 Correct 2 ms 9052 KB Output is correct
14 Correct 2 ms 9052 KB Output is correct
15 Correct 2 ms 9052 KB Output is correct
16 Correct 2 ms 9052 KB Output is correct
17 Correct 2 ms 9052 KB Output is correct
18 Correct 2 ms 9052 KB Output is correct
19 Correct 2 ms 8796 KB Output is correct
20 Correct 2 ms 8796 KB Output is correct
21 Correct 10 ms 9788 KB Output is correct
22 Incorrect 18 ms 11100 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9048 KB Output is correct
2 Correct 3 ms 9052 KB Output is correct
3 Correct 2 ms 9052 KB Output is correct
4 Correct 2 ms 9052 KB Output is correct
5 Correct 2 ms 9052 KB Output is correct
6 Correct 2 ms 8892 KB Output is correct
7 Correct 2 ms 8888 KB Output is correct
8 Correct 2 ms 9052 KB Output is correct
9 Correct 2 ms 9052 KB Output is correct
10 Correct 3 ms 9052 KB Output is correct
11 Correct 2 ms 9052 KB Output is correct
12 Correct 2 ms 9052 KB Output is correct
13 Correct 2 ms 9052 KB Output is correct
14 Correct 2 ms 9052 KB Output is correct
15 Correct 2 ms 9052 KB Output is correct
16 Correct 2 ms 9052 KB Output is correct
17 Correct 2 ms 9052 KB Output is correct
18 Correct 2 ms 9052 KB Output is correct
19 Runtime error 2092 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9048 KB Output is correct
2 Correct 3 ms 9052 KB Output is correct
3 Correct 2 ms 9052 KB Output is correct
4 Correct 2 ms 9052 KB Output is correct
5 Correct 2 ms 9052 KB Output is correct
6 Correct 2 ms 8892 KB Output is correct
7 Correct 2 ms 8888 KB Output is correct
8 Correct 2 ms 9052 KB Output is correct
9 Correct 2 ms 9052 KB Output is correct
10 Correct 3 ms 9052 KB Output is correct
11 Correct 2 ms 9052 KB Output is correct
12 Correct 2 ms 9052 KB Output is correct
13 Correct 2 ms 9052 KB Output is correct
14 Correct 2 ms 9052 KB Output is correct
15 Correct 2 ms 9052 KB Output is correct
16 Correct 2 ms 9052 KB Output is correct
17 Correct 2 ms 9052 KB Output is correct
18 Correct 2 ms 9052 KB Output is correct
19 Correct 2 ms 8796 KB Output is correct
20 Correct 2 ms 8796 KB Output is correct
21 Correct 10 ms 9788 KB Output is correct
22 Incorrect 18 ms 11100 KB Output isn't correct
23 Halted 0 ms 0 KB -