Submission #1177063

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177063		iulia_morariu	Race (IOI11_race)	C++20	21 / 100	3097 ms	48364 KiB

race

#include <algorithm>
#include <iostream>
#include <fstream>
#include <climits>
#include <vector>
#include <stack>
#include <cmath>
#include <map>
#include "race.h"
//#include <bits/stdc++.h>
#define in  cin
#define out cout
#define mkp make_pair

using namespace std;
using ll = long long;

ll n, k, mini = -1;
vector<ll> g[200001], d[200001];
int dim[200001]; // size (local calculat) (you'll see)
int dp[200001]; // dp[i] = dim max a unui subarb daca il elimin pe i (tot local) (you'll also see)
bool acc[200001];

void det_size(int nod, int f){
    dim[nod] = 0;
    for(int cop : g[nod]){
        if(cop == f || !acc[cop]) continue;
        det_size(cop, nod);
        dim[nod] += dim[cop];
    }
    dim[nod]++;
}

void det_dp(int nod, int f, int size_subt){
    dp[nod] = size_subt - dim[nod];
    for(int cop : g[nod]){
        if(cop == f || !acc[cop]) continue;
        det_dp(cop, nod, size_subt);
        dp[nod] = max(dp[nod], dim[cop]);
    }
}

int centroidul(int nod, int f, int size_subt){
    if(dp[nod] <= size_subt / 2) return nod;
    for(int cop : g[nod]){
        if(cop == f || !acc[cop]) continue;
        int cc = centroidul(cop, nod, size_subt);
        if(cc != -1) return cc;
    }
    return -1;
}

void mergeLeft(map< ll, int > & a, map< ll, int > & b, int add){
    for(auto i : b){
        if(i.first + add > k) continue;
        auto it = a.find(i.first + add);
        if(it == a.end()) a[ i.first + add ] = i.second + 1;
        else (*it).second = min((*it).second, i.second + 1);
    }
}

map< ll, int > drumuri(int nod, int f){
    map<ll, int> sol;
    sol[0] = 0;
    int poz = 0;
    for(int cop : g[nod]){
        if(cop == f || !acc[cop]){ poz++; continue; }
        map<ll, int> mp = drumuri(cop, nod);
        mergeLeft(sol, mp, d[nod][poz]);
        poz++;
    }
    return sol;
}

void proc_arb(int nod){
    // cout << "Procesam subarborele lui " << nod << '\n';
    det_size(nod, -1); det_dp(nod, -1, dim[nod]);
    int cen = centroidul(nod, -1, dim[nod]);
    // cout << "  -- > dp : " << dp[1] << " size = " << dim[1] << '\n';
    // cout << "  -- > gasim centroidul ca " << cen << '\n';
    acc[cen] = 0;

    // gasim mapurile
    int poz = 0;
    map<ll, int> general;
    for(int cop : g[cen]){
        if(!acc[cop]){ poz++; continue;}
        map<ll, int> mp = drumuri(cop, cen);
        // cout << "  -- > Facem copilul " << cop << '\n';
        // cout << "  -- > Are ca drumuri pe : \n";
        // for(auto i : mp){
        //     cout << "    -- > " << i.first << " , " << i.second << '\n';
        // }

        for(auto i : mp){
            if(general.find( k - i.first - d[cen][poz] ) == general.end()) continue;
            int len = general[k - i.first - d[cen][poz] ] + i.second + 1;
            // cout << "  -- > Gasesc drum de lungime " << len << '\n';
            if(mini == -1 || mini > len) mini = len;
        }
        
        mergeLeft(general, mp, d[cen][poz]);
        poz++;
    }

    // cout << "In general : \n";
    // for(auto i : general){
    //     cout << "    -- > " << i.first << " , " << i.second << '\n';
    // }

    if( general.find(k) != general.end() && (mini == -1 || general[k] < mini) ) mini = general[k];

    for(int cop : g[cen]){
        if(!acc[cop]) continue;
        proc_arb(cop);
    }
}

int best_path(int N, int K, int H[][2], int L[]){
    n = N; k = K;
    for(int i = 0; i < n; i++) acc[i] = 1;
    for(int i = 0; i < N - 1; i++){
        g[ H[i][0] ].push_back( H[i][1] );
        g[ H[i][1] ].push_back( H[i][0] );

        d[ H[i][0] ].push_back( L[i] );
        d[ H[i][1] ].push_back( L[i] );
    }
    // det_size_si_dp(0, -1);
    // cout << "Pentru graful initial, centroidul este : " << centroidul(0, -1) << '\n'; // okke, merge

    proc_arb(0);
    return mini;
}

// signed main(){
//     ios_base::sync_with_stdio(false);
//     cin.tie(NULL);

//     int n, k; in >> n >> k;
//     int H[n - 1][2], L[n - 1];

//     for(int i = 0; i < n - 1; i++) in >> H[i][0] >> H[i][1];
//     for(int i = 0; i < n - 1; i++) in >> L[i];

//     out << best_path(n, k, H, L) << '\n';

//     return 0;
// }

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