Submission #1179361

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179361		ema_nicole	Race (IOI11_race)	C++17	43 / 100	3103 ms	289188 KiB

race

#include <iostream>
#include <vector>
#include <unordered_map>
#include <map>

using namespace std;
const int NMAX = 200002;
using ll = long long;
const int INF = 21e8;

struct muchii {
    int nod, dist;
};
vector <vector <muchii>> v;
int n, k;

int parent[NMAX];
int weight[NMAX]; ///ce weight are subarb resp
void dfssize(int start) {
    weight[start] = 0;
    for(auto x : v[start]) {
        if(x.nod == parent[start])
            continue;
        parent[x.nod] = start;
        dfssize(x.nod);
        weight[start] += weight[x.nod];
    }
    weight[start]++;
}
int centroid = -1;
void dfscentroid(int start, int sizee) { ///sizeul e de sus
    bool ok = 0;
    if(sizee > n / 2)
        ok = 1;
    for(auto x : v[start]) {
        if(x.nod == parent[start])
            continue;
        if(weight[x.nod] > n / 2)
            ok = 1;
    }
    if(!ok) { ///am gasit centroidul
        centroid = start;
        return;
    }
    for(auto x : v[start]) {
        if(x.nod == parent[start])
            continue;
        dfscentroid(x.nod, sizee + weight[start] - weight[x.nod]);
    }
}

unordered_map <ll, int> umap[NMAX];
int ans = INF; ///dist minima pt suma k

void updateans(int start) {
    unordered_map <ll, int> lg;
    lg.clear();
    if(umap[start].find(k) != umap[start].end()) ///dc deja e lant pana in el
        ans = min(ans, umap[start][k]);
    for(auto x : v[start]) {
        if(x.nod == parent[start])
            continue;
        for(auto var : umap[x.nod]) { ///COMPARAM cu ce avem de la vechii fii
            if(lg.find(k - var.first - x.dist) != lg.end()) {
                ans = min(ans, lg[k - var.first - x.dist] + var.second + 1);
                //if(start == centroid)
                    //cout << var.first << " "
            }
        }
        for(auto var : umap[x.nod]) { ///UPDATAM
            if(var.first + x.dist > k)
                continue;
            if(lg.find(var.first + x.dist) != lg.end())
                lg[var.first + x.dist] = min(lg[var.first + x.dist], var.second + 1);
            else
                lg[var.first + x.dist] = var.second + 1;
        }
    }
}

void dfsans(int start) {
    bool ok = 0;
    for(auto x : v[start]) {
        if(x.nod == parent[start])
            continue;
        dfsans(x.nod);
        ok = 1;
        for(auto var : umap[x.nod]) { ///updatam distantele din x.nod
            if(var.first + x.dist > k)
                continue;
            ///first = distanta, second = cate muchii
            if(umap[start].find(var.first + x.dist) != umap[start].end())
                umap[start][var.first + x.dist] = min(umap[start][var.first + x.dist], var.second + 1);
            else
                umap[start][var.first + x.dist] = var.second + 1;
        }
        umap[start][x.dist] = 1;
    }
    if(!ok) ///frunza
        umap[start][0] = 0;
    else ///cautam dc exista drumuri de suma k
        updateans(start);
    for(auto x : v[start]) { ///stergem mapurile din fii ca nu ne mai pasa
        if(x.nod == parent[start])
            continue;
        umap[x.nod].clear();
    }
    /*cout << "NODUL " << start << '\n';
    for(auto var : umap[start])
        cout << var.first << " " << var.second << '\n';*/
}

int best_path(int N, int K, int h[NMAX][2], int l[NMAX]) {
    n = N, k = K;
    v.resize(n + 1);
    for(int i = 0; i < n - 1; i++) {
        v[h[i][0]].push_back({h[i][1], l[i]});
        v[h[i][1]].push_back({h[i][0], l[i]});
    }
    /*for(int i = 0; i < n; i++) {
        cout << "nodul " << i << '\n';
        for(auto x : v[i])
            cout << x.nod << " ";
        cout << '\n';
    }*/
    parent[0] = -1;
    dfssize(0);
    /*for(int i = 0; i < n; i++)
        cout << weight[i] << " ";
    cout << '\n';*/
    dfscentroid(0, 0);
    parent[centroid] = -1;
    dfssize(centroid); ///reindexam parintii
    /*for(int i = 0; i < n; i++)
        cout << parent[i] << " ";
    cout << '\n';*/
    dfsans(centroid);
    /*for(int i = 48; i < 51; i += 2) {
        cout << "NODUL " << i << '\n';
        for(auto var : umap[i])
            cout << var.first + (i - 1) % 2 << " " << var.second << '\n';
        //if(umap[i].find(k) != umap[i].end())
            //cout << "NODUL " << i << "  " << umap[i][k] << '\n';
    }*/
    if(ans == INF)
        ans = -1;
    return ans;
}

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