Submission #1115743

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115743		lambd47	Race (IOI11_race)	C++17	0 / 100	4 ms	4688 KiB

race

#include "race.h"
#include<bits/stdc++.h>

using namespace std;

const int MOD=1e9+7;
const int MX=1e2+6;
vector<pair<int,int>> adj[MX];
vector<pair<int,int>> vec;
vector<int> limpa;
bool marc[MX];
int sz[MX];
int p[100*MX];

int k;
int n;

int dfssz(int node, int pai){
    sz[node]=1;
    for(auto [a,_]: adj[node]){
        if(a==pai || marc[a])continue;
        sz[node]+=dfssz(a,node);
    }
    return sz[node]; 

}

int findcent(int node, int s, int pai){
    for(auto [a,_]: adj[node]){
        if(a==pai || marc[a])continue;
        if((2*sz[a])>s)return findcent(a,s,node);
    }
    return node;
}

void dfs(int node, int pai, int d,int prof){
    vec.push_back({d,prof});
    limpa.push_back(d);
    for(auto [a,w]:adj[node]){
        if(a==pai || marc[a])continue;
        dfs(a,node,d+w,prof+1);
    }
}

int resp;


void centroidDecomp(int node){
    int s=dfssz(node,node);
    node=findcent(node,s,node);

    marc[node]=1; 
    p[0]=0;
    
    for(auto [a,w]: adj[node]){
        if(marc[a])continue;
        vec.clear();
        dfs(a,node,w,1);
        for(auto [d,prof]:vec){
            if(k>=d && p[k-d]!=MOD){
                resp=min(resp,prof+p[k-d]);
            }
        }
        for(auto [d,prof]:vec){
            p[d]=min(p[d],prof);
        }

    }
    for(auto a: limpa){
        p[a]=MOD;
    }
    limpa.clear();
    for(auto [a,_]:adj[node]){
        if(marc[a])continue;
        centroidDecomp(a);
    }


}





int best_path(int N, int K, int H[][2], int L[])
{
    k=K;
    n=N;
    resp=MOD;
    for(int i=1;i<100*MX;i++)p[i]=MOD;
    for(int i=0;i<n;i++){
        int a=H[i][0],b=H[i][1];
        adj[a].push_back({b,L[i]});
        adj[b].push_back({a,L[i]});
    }
    centroidDecomp(0);
    if(resp==MOD)return -1;



    return resp;
}

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