oj.uz

Submission #1115742

# Submission time Handle Problem Language Result Execution time Memory
1115742 2024-11-20T21:43:36 Z lambd47 Race (IOI11_race) C++17
0 / 100
 150 ms 177664 KB 
#include "race.h"
#include<bits/stdc++.h>

using namespace std;

const int MOD=1e9+7;
const int MX=2e5+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.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 87724 KB Output is correct
2 Correct 54 ms 87780 KB Output is correct
3 Correct 48 ms 87880 KB Output is correct
4 Correct 47 ms 87880 KB Output is correct
5 Runtime error 150 ms 177664 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 87724 KB Output is correct
2 Correct 54 ms 87780 KB Output is correct
3 Correct 48 ms 87880 KB Output is correct
4 Correct 47 ms 87880 KB Output is correct
5 Runtime error 150 ms 177664 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 87724 KB Output is correct
2 Correct 54 ms 87780 KB Output is correct
3 Correct 48 ms 87880 KB Output is correct
4 Correct 47 ms 87880 KB Output is correct
5 Runtime error 150 ms 177664 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 87724 KB Output is correct
2 Correct 54 ms 87780 KB Output is correct
3 Correct 48 ms 87880 KB Output is correct
4 Correct 47 ms 87880 KB Output is correct
5 Runtime error 150 ms 177664 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -