Submission #1177244

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177244		iulia_morariu	Race (IOI11_race)	C++20	0 / 100	10 ms	22336 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

using namespace std;

struct node{
    int lant, offsetS, offsetL;
    map<int, int> mp; // mp[suma] = lungime minima
};

int n, k, mini = -1;
vector<int> g[200001], d[200001];
node v[200001];

void solutie(int nod, int f){ // rezolv subarb lui nod
    v[nod].mp.clear();
    int greu = -1;
    v[nod].lant = 0;
    int poz = 0;
    for(int cop : g[nod]){
        if(cop == f){ poz++; continue;}
        solutie(cop, nod);
        if(greu == -1 || v[cop].lant + 1 > v[nod].lant){
            v[nod].lant = v[cop].lant + 1;
            v[nod].offsetS = d[nod][poz] + v[cop].offsetS;
            v[nod].offsetL = v[cop].offsetL + 1;
            greu = cop;
        }
        poz++;
    }

    // cout << "  -- > copil greu este " << greu << " pentru nodul " << nod << " la tatal " << f << '\n';

    if(greu == -1){
        v[nod].lant = 1;
        v[nod].mp[0] = 0;
        v[nod].offsetS = 0;
        v[nod].offsetL = 0;
        return;
    }
    v[nod].mp = v[greu].mp;

    // cout << "Calculez la " << nod << " f = " << f << '\n';
    // cout << "  -- > Iterez copiii\n";

    poz = 0;
    for(int cop : g[nod]){
        if(cop == f || cop == greu){ poz++; continue; }
        
        // cout << "    -- > Copilul " << cop << " genereaza mp :\n";
        // for(auto i : v[cop].mp){
        //     cout << "      -- > " << i.first << " , " << i.second << '\n';
        // }

        for(auto i : v[cop].mp){
            if( v[nod].mp.find( k - (i.first + v[cop].offsetS) - d[nod][poz] - v[nod].offsetS ) == v[nod].mp.end() ) continue;
            int len = v[nod].mp[ k - (i.first + v[cop].offsetS) - d[nod][poz] - v[nod].offsetS ] + v[nod].offsetL + i.second + 1;
            if(mini == -1 || mini > len) mini = len;
        }

        for(auto i : v[cop].mp){
            // cout << "  -- > facem suma " << i.first + d[nod][poz] + v[cop].offsetS << " ( - " << v[nod].offsetS << " ) si lungimea " << i.second + v[cop].offsetL + 1 << " ( - " << v[nod].offsetL << " )\n";
            if( v[nod].mp.find(i.first + d[nod][poz] + v[cop].offsetS - v[nod].offsetS) == v[nod].mp.end() ){
                v[nod].mp[i.first + d[nod][poz] + v[cop].offsetS - v[nod].offsetS] = i.second + v[cop].offsetL - v[nod].offsetL + 1;
            }else{
                v[nod].mp[i.first + d[nod][poz] + v[cop].offsetS - v[nod].offsetS] = min(v[nod].mp[i.first + d[nod][poz] + v[cop].offsetS - v[nod].offsetS], i.second + v[cop].offsetL - v[nod].offsetL + 1);
            }
        }
        poz++;
    }
    
    // cout << "Nod = " << nod << " f = " << f << " offsetS = " << v[nod].offsetS << " offsetL = " << v[nod].offsetL << " v[nod].mp =\n";
    // for(auto i : v[nod].mp){
    //     cout << "  -- > " << i.first + v[nod].offsetS << " , " << i.second + v[nod].offsetL << '\n';
    // }

    if(v[nod].mp.find(k - v[nod].offsetS) != v[nod].mp.end()){
        if(mini == -1) mini = v[nod].mp[ k - v[nod].offsetS ] + v[nod].offsetL;
        else mini = min(mini, v[nod].mp[ k - v[nod].offsetS ] + v[nod].offsetL);
    }
}

int best_path(int N, int K, int H[][2], int L[]){
    n = N; k = K;
    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] );
    }

    solutie(0, -1);

    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];
//     out << best_path(n, k, H, L);

//     return 0;
// }

// // The Thing

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