제출 #449912

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
449912		vishalagrawal	경주 (Race) (IOI11_race)	C++14	100 / 100	1538 ms	84084 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 (long long i = 0; i < (long long)arr.size(); i++)
    {
        os << arr[i] << " ";
    }
    return os << "";
}

template <class T>
ostream &operator<<(ostream &os, vector<vector<T>> matrix)
{
    os << endl;
    for (long long i = 0; i < (long long)matrix.size(); i++)
    {
        for (long long j = 0; j < (long long)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 << "key: " << m.first << endl;
        os << "value: " << m.second << 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 long long max_n = 2e5 + 10;
vector<vector<long long>> adj;
vector<vector<pair<long long, long long>>> g;
map<long long, multiset<long long>> vals;
long long depth[max_n];
long long arr[max_n];
long long sz[max_n];
long long heavy = -1;
long long K;
long long ans = 1e9;

long long sack_size(long long node, long long cur_depth, long long cur, long long parent = 0)
{
    arr[node] = cur;
    depth[node] = cur_depth;
    sz[node] = 1;
    long long max_sz = 0;
    for (long long i = 0; i < (long long)g[node].size(); i++)
    {
        if (g[node][i].first == parent)
        {
            continue;
        }
        long long 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(long long node, long long parent, long long root, long long type)
{
    if (type == 0)
    {
        vals[arr[node]].erase(vals[arr[node]].find(depth[node]));
        if (vals[arr[node]].size() == 0)
        {
            vals.erase(arr[node]);
        }
    }
    else if (type == 1)
    {
        long long need = K - arr[node] + 2 * arr[root];
        if (vals.find(need) != vals.end())
        {
            long long temp = *vals[need].begin() + depth[node] - 2 * depth[root];
            if (ans > temp)
            {
                ans = temp;
            }
        }
    }
    else
    {
        vals[arr[node]].insert(depth[node]);
    }

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

void sack_dfs(long long node, long long parent, long long keep)
{
    for (long long i = 1; i < (long long)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];
    }

    vals[arr[node]].insert(depth[node]);
    long long need = K + arr[node];
    if (vals.find(need) != vals.end())
    {
        long long temp = *vals[need].begin() - depth[node];
        if (ans > temp)
        {
            ans = temp;
        }
    }

    for (long long i = 1; i < (long long)adj[node].size(); i++)
    {
        if (adj[node][i] != parent)
        {
            sack_add(adj[node][i], node, node, 1);
            sack_add(adj[node][i], node, node, 2);
        }
    }

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

int best_path(int N_temp, int K_temp, int (*edge)[2], int *weight)
{
    long long N = N_temp;
    K = K_temp;

    g.resize(N + 1);
    adj.resize(N + 1);
  
    for (long long i = 0; i < N - 1; i++)
    {
        edge[i][0]++;
        edge[i][1]++;
        g[edge[i][0]].push_back({edge[i][1], weight[i]});
        g[edge[i][1]].push_back({edge[i][0], weight[i]});
        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)
    {
        ans = -1;
    }

    return ans;
}

// long long32_t main()
// {
//     ios_base::sync_with_stdio(false);
//     cin.tie(NULL);
//     long long no_of_testcases = 1;
//     // cin >> no_of_testcases;
//     for (long long i = 1; i <= no_of_testcases; i++)
//     {
//         // cout << "Case #" << i << ": ";
//         solve();
//     }
//     return 0;
// }

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