Submission #712013

#	Time	Username	Problem	Language	Result	Execution time	Memory
712013		Hoff22	Race (IOI11_race)	C++14	21 / 100	174 ms	41752 KiB

race

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

using namespace std;

typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

#define FOR(i,a) for (int i=0; i<(a); i++)
#define FORI(i,a,b) for (int i=a; i<(b); i++)
#define FORd(i,a) for (int i=(a)-1; i>=0; i--)
#define FORId(i,a,b) for (int i=(a)-1; i>=(b); i--)
#define trav(a,x) for (auto& a : x)
#define uid(a,b) uniform_int_distribution<int>(a, b)(rng)
#define printv(i,x) trav(i,x) cout << i << " "; cout << "\n";

#define sz(x) (int) (x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define ins insert

#define LEFT(x) (2*x)
#define RIGHT(x) (2*x+1)

const int MOD = 998244353;
const int INF = 0x3f3f3f3f;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;

#define MAX 100000

int num_of_vertices,kilometers;
vi edges[MAX], costs[MAX];

vector<set<ll>> sumk(MAX);
vector<map<ll,int>> highway(MAX);
vi sub_size(MAX);

int ans, mini = INF;

void p(int u, ll cost, int qnts, int ant)
{
    // cout << u << " " << ant << "\n";

    int maxi = -1, qual = -1;
    FOR(i,sz(edges[u]))
    {
        int v = edges[u][i];
        int w = costs[u][i];
        if (v == ant) continue;

        p(v,cost+w,qnts+1,u);

        if (sub_size[v] > maxi)
        {
            maxi = sub_size[v];
            qual = v;
        }
    }

    // cout << u << " " << ant << ":\n";
    // cout << qual << " " << maxi << "\n";

    if (qual != -1)
    {
        swap(sumk[u],sumk[qual]); // O(1)
        swap(highway[u],highway[qual]);
        sub_size[u] = sub_size[qual];

        // Query
        if (sumk[u].count(kilometers+cost))
            mini = min(mini,highway[u][kilometers+cost]-qnts);

        // Update
        if (sumk[u].count(cost) == 0)
            sumk[u].insert(cost);
        highway[u][cost] = qnts;

        sub_size[u]++;

        FOR(i,sz(edges[u]))
        {
            int v = edges[u][i];
            if (v == qual or v == ant) continue;
 
            for (auto j : sumk[v])
            {
                // Queries
                if (sumk[u].count(kilometers-(j-cost)+cost))
                    mini = min(mini,highway[u][kilometers-(j-cost)+cost]-qnts + highway[v][j]-qnts);
            }

            for (auto j : sumk[v])
            {
                // Updates
                if (sumk[u].count(j) == 0)
                    sumk[u].insert(j);

                highway[u][j] = highway[v][j];

                sub_size[u]++;
            }
        }
    }
    else
    {
        sub_size[u] = 1;
        sumk[u].insert(cost);
        highway[u][cost] = qnts;

        if (sumk[u].count(kilometers))
            mini = min(mini,qnts);
    }

    // cout << "mini: " << mini << "\n";
    // cout << "sumk de " << u << ": ";
    // for (auto i : sumk[u])
    //     cout << i << " ";
    // cout << "\n";
    // cout << "highway de " << u << ": ";
    // for (auto i : highway[u])
    //     cout << i.f << ": " << i.s << " | ";
    // cout << "\n";
}

int best_path(int n, int k, int (*h)[2], int* l)
{
    FOR(i,n-1)
    {
        edges[i].clear();
        costs[i].clear();

        sumk[i].clear();
        highway[i].clear();
        sub_size[i] = 0;
        mini = INF;
    }

    FOR(i,n-1)
    {
        ll u, v, w;
        u = h[i][0];
        v = h[i][1];
        w = l[i];

        edges[u].pb(v); 
        edges[v].pb(u);

        costs[u].pb(w);
        costs[v].pb(w);
    }

    num_of_vertices = n;
    kilometers = k;

    p(0,0,0,-1);

    ans = mini;
    if (ans == INF)
        ans = -1;
    return ans;
}

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