Submission #140869

#	Time	Username	Problem	Language	Result	Execution time	Memory
140869		silxikys	Race (IOI11_race)	C++14	100 / 100	534 ms	77804 KiB

race

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
#include <map>
using namespace std;
typedef long long ll;

const int maxn = 200005;
const int INF = 999999999;
int n, k;
int ans = 0;
struct Edge {
    int other, weight;    
};
vector<Edge> adj[maxn];

struct Node
{
    map<int,int>* mp;
    int lAux, pathAux;
    int curr;
    inline int sz() {return mp->size();}
    Node() {
        mp = new map<int,int>;
        pathAux = 0;
        lAux = 0;
        curr = INF;
    }
    void addSelf() {
        (*mp)[-lAux] = -pathAux;
    }
    
} nodes[maxn];

void merge(Node& a, Node& b, int weight) {
    b.lAux += weight;
    bool swapped = false;
    if (a.sz() < b.sz()) {
        swap(a,b);
        swapped = true;
    }
    //check for paths
    if (!swapped) {
        if (a.mp->count(k-weight-a.lAux)) {
            int n2 = (*a.mp)[k-weight-a.lAux] + a.pathAux;
            ans = min(ans,1+n2);
        }
    }
    for (auto p: (*b.mp)) {
        int len = p.first + b.lAux;
        int num = p.second + b.pathAux;
        if (a.mp->count(k-len-a.lAux)) {
            int n2 = (*a.mp)[k-len-a.lAux] + a.pathAux;
            ans = min(ans,num+n2);
        }
    }
    //now add the paths
    for (auto p: (*b.mp)) {
        int len = p.first + b.lAux;
        int num = p.second + b.pathAux;
        if (!a.mp->count(len-a.lAux)) {
            (*a.mp)[len-a.lAux] = num-a.pathAux;    
        }
        else if ((*a.mp)[len-a.lAux] > num-a.pathAux) {
            (*a.mp)[len-a.lAux] = num-a.pathAux;
        }
    }
    //add the path from a to b itself
    if (!swapped) {
        if (!a.mp->count(weight-a.lAux)) {
            (*a.mp)[weight-a.lAux] = 1 - a.pathAux;
        }
        else if ((*a.mp)[weight-a.lAux] > weight-a.pathAux) {
            (*a.mp)[weight-a.lAux] = 1 - a.pathAux;
        }
    }
    delete b.mp;
}

void dfs(int i, int par) {
    nodes[i] = Node();
    nodes[i].addSelf();
    for (Edge e: adj[i]) {
        if (e.other == par) continue;
        dfs(e.other,i);
        merge(nodes[i],nodes[e.other],e.weight);
    }
    nodes[i].pathAux++;
}

int best_path(int N, int K, int H[][2], int L[])
{
    n = N;
    k = K;
    for (int i = 0; i < N - 1; i++) {
        int h1 = H[i][0], h2 = H[i][1], li = L[i];
        adj[h1].push_back({h2,li});
        adj[h2].push_back({h1,li});
    }
    ans = INF;
    dfs(0,-1);
    return (ans == INF ? -1 : ans);
}
	

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