제출 #1177122

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1177122		iulia_morariu	경주 (Race) (IOI11_race)	C++20	100 / 100	1077 ms	64304 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;

ifstream fin("test.in");

ll n, k, mini = -1;
vector<int> 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, int addL){
    for(auto i : b){
        if(i.first + add > k || (mini != -1 && i.second + addL > mini)) continue;
        auto it = a.find(i.first + add);
        if(it == a.end()) a[ i.first + add ] = i.second + addL;
        else (*it).second = min((*it).second, i.second + addL);
    }
}

void drumuri(int nod, int f, map<ll, int> & mp, int offset, int len){ // offset = cat e drumul de la root la mine
    if(offset > k) return;
    if(mini != -1 && len > mini) return;
    
    if(mp.find(offset) != mp.end()) mp[offset] = min(mp[offset], len);
    else mp[offset] = len;

    // cout << "DRUMURI : Am ajuns la " << nod << " parintele " << f << " map (mp) offset = " << offset << " len = " << len << '\n';

    int poz = 0;
    for(int cop : g[nod]){
        if(cop == f || !acc[cop]){ poz++; continue; }
        drumuri(cop, nod, mp, offset + d[nod][poz], len + 1);
        poz++;
    }
}

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

    // gasim mapurile
    int poz = 0;
    // cerr << "Incepem det " << nod << '\n';
    map<ll, int> general;
    for(int cop : g[cen]){
        if(!acc[cop]){ poz++; continue;}
        map<ll, int> mp;
        drumuri(cop, cen, mp, d[cen][poz], 1);

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

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

    // 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;
    // cerr << "Start\n";
    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] );
    }
    // cerr << "End\n";

    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] >> L[i];
//     // 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: 22 / 22
• Subtask 4: 57 / 57