Submission #548580

#	Time	Username	Problem	Language	Result	Execution time	Memory
548580		Sergio_2357	Race (IOI11_race)	C++17	21 / 100	261 ms	10584 KiB

race

#include "race.h"
#include <bits/stdc++.h>

using namespace std;

#define int long long

#define F first
#define S second

typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
typedef vector<vpi> vipi;

bool cmp(tuple<int, int, int> a, tuple<int, int, int> b)
{
    return get<1>(a) < get<2>(b);
}

vpi transverse(int i, int p, int& m_l, int k, vipi& g)
{
    set<int> p_s;
    map<int, vector<tuple<int, int, int>>> res;

    for (auto ot : g[i]) {
        if (ot.F == p)
            continue;
        vpi ret = transverse(get<0>(ot), i, m_l, k, g);
        if (ot.S > k)
            continue;
        p_s.insert(ot.S);
        res[ot.S].push_back({ ot.S, 1, ot.F });
        for (auto pa : ret) {
            if (pa.F + ot.S > k)
                continue;
            if (pa.F == 0)
                continue;
            p_s.insert(pa.F + ot.S);
            res[pa.F + ot.S].push_back({ pa.F + ot.S, pa.S + 1, ot.F });
        }
    }

    if (p_s.count(k)) {
        m_l = min(m_l, get<1>(res[k][0]));
    }

    vi v;
    for (int x : p_s)
        v.push_back(x);

    int a = 0, b = v.size() - 1;
    vpi pairs;
    while (a <= b) {
        if (v[a] + v[b] == k) {
            pairs.push_back({ v[a], v[b] });
            a++;
        } else if (v[a] + v[b] < k) {
            a++;
        } else {
            b--;
        }
    }

    for (int x : p_s)
        sort(res[x].begin(), res[x].end(), cmp);
    for (auto pa : pairs) {
        int c = get<1>(res[pa.F][0]) + get<1>(res[pa.S][0]);
        if (get<2>(res[pa.F][0]) == get<2>(res[pa.S][0])) {
            //cout << "HERE" << endl;
            if (res[pa.F].size() == 1 && res[pa.S].size() == 1)
                continue;
            else if (res[pa.S].size() == 1) {
                c = c - get<1>(res[pa.F][0]) + get<1>(res[pa.F][1]);
            } else if (res[pa.F].size() == 1) {
                c = c - get<1>(res[pa.S][0]) + get<1>(res[pa.S][1]);
            } else {
                int c1 = c - get<1>(res[pa.F][0]) + get<1>(res[pa.F][1]);
                int c2 = c - get<1>(res[pa.S][0]) + get<1>(res[pa.S][1]);
                c = min(c1, c2);
            }
        }
        //cout << pa.F << ' ' << pa.S << " - " << c << endl;
        m_l = min(m_l, c);
    }

    vpi cmp(v.size());
    for (int i = 0; i < v.size(); i++) {
        cmp[i] = { get<0>(res[v[i]][0]), get<1>(res[v[i]][0]) };
        //cout << cmp[i].F << " - " << cmp[i].S << ", ";
    }
    //cout << endl;
    //cout << i << ' ' << m_l << endl;
    return cmp;
}

signed best_path(signed N, signed K, signed H[][2], signed L[])
{
    int n = N;
    int k = K;
    vipi g(n);
    for (int i = 0; i < n - 1; i++) {
        int u = H[i][0];
        int v = H[i][1];
        int w = L[i];
        g[u].push_back({ v, w });
        g[v].push_back({ u, w });
    }
    int m_l = LLONG_MAX;
    transverse(0, -1, m_l, k, g);
    if (m_l == LLONG_MAX)
        return -1;
    return (signed)m_l;
}

Compilation message (stderr)

race.cpp: In function 'vpi transverse(long long int, long long int, long long int&, long long int, vipi&)':
race.cpp:89:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     for (int i = 0; i < v.size(); i++) {
      |                     ~~^~~~~~~~~~

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