Submission #805350

#	Time	Username	Problem	Language	Result	Execution time	Memory
805350		Boomyday	Race (IOI11_race)	C++17	0 / 100	1 ms	212 KiB

race

//
// Created by adavy on 2/11/2023.
//
#include <bits/stdc++.h>
#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

using ll = long long;
using ld = long double;
using db = double;
using str = string; // yay python!

using ii = pair<int,int>;
using pl = pair<ll,ll>;
using pd = pair<db,db>;

using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>;
using vs = vector<str>;
using vii = vector<ii>;
using vpl = vector<pl>;
using vpd = vector<pd>;

#define tcT template<class T
#define tcTU tcT, class U

tcT> using V = vector<T>;
tcT, size_t SZ> using AR = array<T,SZ>;
tcT> using PR = pair<T,T>;

// pairs
#define mp make_pair
#define f first
#define s second

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

#define len(x) int((x).size())
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define sor(x) sort(all(x))
#define rsz resize
#define ins insert
#define ft front()
#define bk back()
#define pb push_back
#define eb emplace_back
#define pf push_front

const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5;
const ll INF = 1e18; // not too close to LLONG_MAX
const ld PI = acos((ld)-1);
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1}; // for every grid problem!!

vector<vector<pair<ll,ll>>> adj;
vl sz,dep,dist;
vb vis;
ll D;


ll bestD = INF;

int init_sz(int nd, int par=-1){
    if (vis[nd]) return 0;
    sz[nd] = 1;
    trav(nei, adj[nd]) if (nei.s!=par) sz[nd] += init_sz(nei.s,nd);
    return sz[nd];
}

int find_centroid(int nd, int par, ll num){
    trav(nei, adj[nd]) if (nei.s != par) if (!vis[nei.s]&&sz[nei.s]>num/2) return find_centroid(nei.s, nd, num);
    return nd;
}

void dfs(int nd, int par,map<ll,ll>& mp,vector<pair<ll,ll>>& prl){



   if (mp.find(D-dist[nd])==mp.end()) mp[D-dist[nd]] = INF;
   bestD = min(bestD,dep[nd]+mp[D-dist[nd]]);
   prl.pb({dist[nd],dep[nd]});

    trav(nei, adj[nd]) if (nei.s != par) if (!vis[nei.s]) {
        dep[nei.s] = dep[nd] + 1;
        dist[nei.s] = dep[nd] + nei.f;
    }
}

void init_centroid(int nd, int par=-1){
    init_sz(nd);
    int c = find_centroid(nd, -1, sz[nd]);
    vis[c] = 1;



    map<ll,ll> mp; //weighted, unweighted


    trav(nei, adj[c]) if (!vis[nei.s]) {
        vector<pair<ll,ll>> prl;
            dep[nei.s] = 1;
            dist[nei.s] = nei.f;
            dfs(nei.s, -1,mp,prl);

            for(auto&[distL,depL]:prl){
                if (mp.find(distL)==mp.end()) mp[distL] = INF;
                mp[distL] = min(mp[distL],depL);

            }
        }

    trav(nei, adj[c]) if (!vis[nei.s]) init_centroid(nei.s,c);
}

int best_path(int n, int k, int h[][2], int l[])
{
    D = k;
    adj.rsz(n);
    vis.rsz(n);
    sz.rsz(n);
    dep.rsz(n);
    dist.rsz(n);
    fill(all(vis),0);
    F0R(i, n-1){
        adj[h[i][0]].pb({l[i],h[i][1]});
        adj[h[i][1]].pb({l[i],h[i][0]});

    }
    init_centroid(0);
    if (bestD==INF) return -1;
    else return bestD;
}



/*
 * 11 12
0 1 3
0 2 4
2 3 5
3 4 4
4 5 6
0 6 3
6 7 2
6 8 5
8 9 6
8 10 7
2


 */

#include "race.h"
/*
#define MAX_N 500000

static int N, K;
static int H[MAX_N][2];
static int L[MAX_N];
static int solution;

inline
void my_assert(int e) {if (!e) abort();}

void read_input()
{
    int i;
    my_assert(2==scanf("%d %d",&N,&K));
    for(i=0; i<N-1; i++)
        my_assert(3==scanf("%d %d %d",&H[i][0],&H[i][1],&L[i]));
    my_assert(1==scanf("%d",&solution));
}

int main()
{
    int ans;
    read_input();
    ans = best_path(N,K,H,L);
    if(ans==solution)
        printf("Correct.\n");
    else
        printf("Incorrect. Returned %d, Expected %d.\n",ans,solution);

    return 0;
}
*/

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