Submission #484193

#	Time	Username	Problem	Language	Result	Execution time	Memory
484193		FEDIKUS	Race (IOI11_race)	C++17	100 / 100	382 ms	74980 KiB

race

#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#include "race.h"
#include<bits/stdc++.h>
#define xx first
#define yy second
 
using namespace std;
 
const int maxn=2e5+10;
 
vector<pair<int,int> > g[maxn];
pair<pair<int,int> ,map<int,int> > s[maxn];
 
int merges(pair<pair<int,int> ,map<int,int> > &a,pair<pair<int,int> ,map<int,int> > &b,int c,int k){
    b.xx.xx+=c;
    b.xx.yy+=1;
    if(a.yy.size()<b.yy.size()) swap(a,b);
    int ret=INT_MAX;
    for(auto &i:b.yy){
        if(a.yy.find(k-i.xx-b.xx.xx-a.xx.xx)!=a.yy.end())
            ret=min(ret,a.yy[k-i.xx-b.xx.xx-a.xx.xx]+a.xx.yy+i.yy+b.xx.yy);
    }
    for(auto &i:b.yy){
        if(a.yy.find(i.xx+b.xx.xx-a.xx.xx)!=a.yy.end())
            a.yy[i.xx+b.xx.xx-a.xx.xx]=min(a.yy[i.xx+b.xx.xx-a.xx.xx],i.yy+b.xx.yy-a.xx.yy);
        else
            a.yy[i.xx+b.xx.xx-a.xx.xx]=i.yy+b.xx.yy-a.xx.yy;
    }
    return ret;
}
 
int dfs(int cvor,int k,int p=-1){
    int ret=INT_MAX;
    for(pair<int,int> i:g[cvor]){
        if(i.xx==p) continue;
        ret=min(ret,dfs(i.xx,k,cvor));
        ret=min(ret,merges(s[cvor],s[i.xx],i.yy,k));
    }
    s[cvor].yy[-s[cvor].xx.xx]=-s[cvor].xx.yy;
    if(s[cvor].yy.find(k-s[cvor].xx.xx)!=s[cvor].yy.end())
        ret=min(ret,s[cvor].yy[k-s[cvor].xx.xx]+s[cvor].xx.yy);
    return ret;
}
 
int best_path(int n, int k, int h[][2], int l[]){
    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]));
    }
    int ret=dfs(0,k);
    return ret==INT_MAX ? -1:ret;
}

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