Submission #838805

#	Time	Username	Problem	Language	Result	Execution time	Memory
838805		ASN49K	Race (IOI11_race)	C++14	100 / 100	461 ms	79572 KiB

race

#include <iostream>
#include <algorithm>
#include <vector>
#include <cassert>
#include <cmath>
#include <stack>
#include <set>
#include <functional>
#include <bitset>
#include <map>
#include <unordered_map>
#include <queue>
#include <array>
#include <numeric>
using namespace std;
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename A> ostream& operator<<(ostream &os, vector<A>&a) { for(auto &c:a)os<<c<<' '; return os;}
template<typename A> istream& operator>>(istream  &os, vector<A>&a) { for(auto &c:a)os>>c; return os;}
template<typename A,size_t N> istream& operator>>(istream &os, array<A,N>&a) { for(auto &c:a)os>>c; return os;}
template<typename A,typename B> istream& operator>>(istream  &os, pair<A,B>&a) { os>>a.first>>a.second; return os;}
#define bug(a) cerr << "(" << #a << ": " << a << ")\n";
#define all(x) x.begin(),x.end()
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define PQ priority_queue
using pii= pair<int,int>;
using VI= vector<int>;
using v64= vector<int64_t>;
using i64= int64_t;
using i16= int16_t;
using u64= uint64_t;
using u32= uint32_t;
using i32= int32_t;
using u16= uint16_t;
const i32 inf=1e9;
const i64 INF=1e18;
const int mod=1e9+7;
const int sigma=26;
string yn(bool x){if(x)return "YES";return "NO";}

int best_path(int N, int K, int H[][2], int L[])
{
    const int n=N;
    vector<map<int,int>>mp(n);
    vector<vector<pii>>g(n);
    for(int i=0;i<n-1;i++)
    {
        g[H[i][0]].pb({H[i][1],L[i]});
        g[H[i][1]].pb({H[i][0],L[i]});
    }

    int rez= n + 1;
    auto _min=[&](int& x,const int& y)
    {
        if(x>y)
            x=y;
    };
    auto merge=[&](int x,int y,int h,int sum)
    {
        if(mp[x].size()<mp[y].size())
        {
            swap(mp[x],mp[y]);
        }
        for(auto &c:mp[y])
        {
            auto it=mp[x].find(K-(c.first-sum)+sum);
            if(it!=mp[x].end())
            {
                _min(rez,c.second+it->second-2*h);
            }
        }
        for(auto &c:mp[y])
        {
            if(!mp[x].count(c.first))
                mp[x][c.first]=c.second;
            else
                _min(mp[x][c.first],c.second);
        }
    };
    function<void(int,int,int,int)>dfs=[&](int nod,int tt,int h,int sum)
    {
        mp[nod][sum]=h;
        for(auto &c:g[nod])
        {
            if(c.first==tt)
                continue;
            dfs(c.first,nod,h+1,sum+c.second);
            merge(nod,c.first,h,sum);
        }
    };
    dfs(0,0,0,0);
    if(rez==n+1)
        return -1;
    return rez;
}
/*int g[100][2],h[100];
void solve()
{
    int n,k;
    cin>>n>>k;
    for(int i=0;i<n-1;i++)
    {
        cin>>g[i][0]>>g[i][1];
    }
    for(int i=0;i<n-1;i++)
    {
        cin>>h[i];
    }
    cout<<best_path(n,k,g,h);


}
main()
{
    i32 tt=1;
    ios::sync_with_stdio(false);
    cin.tie(0);
    //cin>>tt;
    while(tt--)
    {
        solve();
    }
}*/

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