Submission #449417

#	Time	Username	Problem	Language	Result	Execution time	Memory
449417		vishalagrawal	Race (IOI11_race)	C++14	43 / 100	2183 ms	122420 KiB

race

#include <bits/stdc++.h>

#define endl "\n"
#define double long double
#define precise(x) \
    fixed << setprecision(x)
#ifndef ONLINE_JUDGE
#define debug(var) cerr << (#var) << ": " << var << endl
#else
#define debug(var)
#endif

using namespace std;

template <typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;

template <typename T>
using max_heap = priority_queue<T>;

template <class T>
ostream &operator<<(ostream &os, min_heap<T> H)
{
    while (!H.empty())
    {
        os << H.top() << " ";
        H.pop();
    }
    os << endl;
    return os << "";
}

template <class T>
ostream &operator<<(ostream &os, max_heap<T> H)
{
    while (!H.empty())
    {
        os << H.top() << " ";
        H.pop();
    }
    os << endl;
    return os << "";
}

template <class L, class R>
ostream &operator<<(ostream &os, pair<L, R> P)
{
    return os << P.first << " " << P.second;
}

template <class T>
ostream &operator<<(ostream &os, vector<T> arr)
{
    for (int i = 0; i < (int)arr.size(); i++)
    {
        os << arr[i] << " ";
    }
    return os << "";
}

template <class T>
ostream &operator<<(ostream &os, vector<vector<T>> matrix)
{
    os << endl;
    for (int i = 0; i < (int)matrix.size(); i++)
    {
        for (int j = 0; j < (int)matrix[i].size(); j++)
        {
            os << matrix[i][j] << " ";
        }
        os << endl;
    }
    return os << "";
}

template <class T>
ostream &operator<<(ostream &os, set<T> S)
{
    for (auto s : S)
    {
        os << s << " ";
    }
    return os << "";
}

template <class T>
ostream &operator<<(ostream &os, multiset<T> S)
{
    for (auto s : S)
    {
        os << s << " ";
    }
    return os << "";
}

template <class L, class R>
ostream &operator<<(ostream &os, map<L, R> M)
{
    os << endl;
    for (auto m : M)
    {
        os << m << endl;
    }
    return os << "";
}

template <class L, class R>
ostream &operator<<(ostream &os, multimap<L, R> M)
{
    os << endl;
    for (auto m : M)
    {
        os << m << endl;
    }
    return os << "";
}

const int max_n = 2e5 + 10;
vector<vector<int>> adj;
vector<vector<pair<int, int>>> g;
map<long long, multiset<int>> vals;
int depth[max_n];
long long arr[max_n];
int sz[max_n];
int heavy = -1;
int K;
int ans = 1e9;

int sack_size(int node, int cur_depth, long long cur, int parent = 0)
{
    arr[node] = cur;
    depth[node] = cur_depth;
    sz[node] = 1;
    int max_sz = 0;
    for (int i = 0; i < (int)g[node].size(); i++)
    {
        if (g[node][i].first == parent)
        {
            continue;
        }
        int temp = sack_size(g[node][i].first, cur_depth + 1, cur + g[node][i].second, node);
        sz[node] += temp;
        if (temp > max_sz)
        {
            max_sz = temp;
            swap(adj[node][0], adj[node][i]);
        }
    }
    return sz[node];
}

void sack_add(int node, int parent, int root, int type)
{
    if (type == 0)
    {
        vals[arr[node]].erase(vals[arr[node]].find(depth[node]));
    }
    else
    {
        long long need = K - arr[node] + 2 * arr[root];
        if (vals[need].size() != 0)
        {
            ans = min(ans, *vals[need].begin() + depth[node] - 2 * depth[root]);
        }
        vals[arr[node]].insert(depth[node]);
    }

    for (int i = 0; i < (int)adj[node].size(); i++)
    {
        if (adj[node][i] != parent && adj[node][i] != heavy)
        {
            sack_add(adj[node][i], node, root, type);
        }
    }
}

void sack_dfs(int node, int parent, int keep)
{
    for (int i = 1; i < (int)adj[node].size(); i++)
    {
        if (adj[node][i] != parent)
        {
            sack_dfs(adj[node][i], node, 0);
        }
    }

    if (sz[node] != 1)
    {
        sack_dfs(adj[node][0], node, 1);
        heavy = adj[node][0];
    }

    sack_add(node, parent, node, 1);

    heavy = -1;
    if (!keep)
    {
        sack_add(node, parent, node, 0);
    }
}

int best_path(int temp_N, int temp_K, int (*edge)[2], int* L)
{
    int N = temp_N;
    K = temp_K;
    for (int i = 0; i < N - 1; i++)
    {
        edge[i][0]++;
        edge[i][1]++;
    }

    g.resize(N + 1);
    adj.resize(N + 1);

    for (int i = 0; i < N - 1; i++)
    {
        int weight = L[i];
        g[edge[i][0]].push_back({edge[i][1], weight});
        g[edge[i][1]].push_back({edge[i][0], weight});
        adj[edge[i][0]].push_back(edge[i][1]);
        adj[edge[i][1]].push_back(edge[i][0]);
    }

    sack_size(1, 1, 1);
    sack_dfs(1, 0, 0);

    if (ans == 1e9)
    {
        return -1;
    }
    return ans;
}

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