Submission #825308

#	Time	Username	Problem	Language	Result	Execution time	Memory
825308		YassirSalama	Race (IOI11_race)	C++17	21 / 100	3055 ms	103928 KiB

race

//It's not my solution
#include <bits/stdc++.h>
#include "race.h"
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,bmi,bmi2,popcnt,lzcnt")
using ll =long long;
//#define int ll
ll LINF=1000000000000000000;
int INF=1e9;
#define pi pair<int,int>
#define pl pair<ll,ll>
#define endl '\n'
#define vi vector<int>
#define vii vector<vector<int>>
#define vl vector<ll>
#define vll vector<vector<ll>>
//#define int ll
using namespace std;
vector<vector<pi>>g;
int k;
int minimum=INF;
 
vi vinf={INF,-1};
 
 
void add(map<int,vii>&v,map<int,vii>&cv,int node,int dist){
    for(auto itr=cv.begin();itr!=cv.end() && itr->first+dist<k+1;itr++){
        if(itr->second[1][0]+1>=minimum)continue;
        auto itr2=v.find(itr->first+dist);
        if(itr2==v.end()){
            auto vect=vii(2,vi({INF,-1}));
            v[itr->first+dist]=vect;
            itr2=v.find(itr->first+dist);
        }
        if(itr2->second[0][0]>itr->second[1][0]+1){
            itr2->second[0][0]=itr->second[1][0]+1;
            itr2->second[0][1]=node;
            if(itr2->second[0][0]<itr2->second[1][0]){
                swap(itr2->second[0][0],itr2->second[1][0]);
                swap(itr2->second[0][1],itr2->second[1][1]);
            }
        }
    }
}
 
map<int,vii> dfs(int node,int parent){
    map<int,vii>m;
    m.insert(make_pair(0,vii({vi({INF,-1}),vi({0,node})})));
    for(pi child:g[node]){
        if(child.first==parent)continue;
        auto cv=dfs(child.first,node);
        add(m,cv,child.first,child.second);
        cv.clear();
    }
    for(auto itr=m.begin();itr!=m.end();itr++){
        auto itr2=m.find(k-itr->first);
        if(itr2!=m.end()){
            if(itr2->second[1][1]!=itr->second[1][1]){
                minimum=min(minimum,itr2->second[1][0]+itr->second[1][0]);
            }
            else {
                minimum=min(minimum,itr2->second[0][0]+itr->second[1][0]);
            }
        }
    }
    return m;
}
 
 
int best_path(int N, int K, int H[][2], int L[])
{
    g.resize(N);
    k=K;
    for(int i=0;i<N-1;i++){
        g[H[i][0]].push_back(make_pair(H[i][1],L[i]));
        g[H[i][1]].push_back(make_pair(H[i][0],L[i]));
    }
    dfs(0,-1);
 
 
    if(minimum==1e9)return -1;
    return minimum;
}

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