Submission #446117

#	Time	Username	Problem	Language	Result	Execution time	Memory
446117		Deepesson	Race (IOI11_race)	C++17	0 / 100	10 ms	14816 KiB

race

#include "race.h"

#include <bits/stdc++.h>
#define MAX 205000
typedef std::pair<int,int> pii;
int NA,KA;
std::vector<pii> con[MAX];
std::map<int,long long> mapa[MAX];
long long count=0;
void merge(int a,int b) {
    if(mapa[a].size()<mapa[b].size())std::swap(mapa[a],mapa[b]);
    for(auto&x:mapa[b]){
        {
            auto it = mapa[a].find(x.first+KA);
            if(it!=mapa[a].end())count+=it->second;
        }
        {
            auto it = mapa[a].find(x.first-KA);
            if(it!=mapa[a].end())count+=it->second;
        }
    }
    for(auto&x:mapa[b])mapa[a][x.first]+=x.second;
}
void dfs(int pos,int prev,int dist) {
    mapa[pos][dist]++;
    for(auto&x:con[pos]){
        if(prev==x.first)continue;
        dfs(x.first,pos,dist+x.second);
        merge(pos,x.first);
    }
}
int best_path(int N, int K, int H[][2], int L[])
{
    for(auto&x:mapa)x.clear();
    for(auto&x:con)x.clear();
    NA=N;KA=K;
    for(int i=0;i!=N-1;++i){
        int a,b,c;
        a=H[i][0],b=H[i][1],c=L[i];
        con[a].push_back({b,c});
        con[b].push_back({a,c});
    }
    dfs(0,-1,0);
    if(!count)count=-1;
    return count;
}

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