Submission #1099529

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099529		Mr_Roamer	Race (IOI11_race)	C++17	0 / 100	37 ms	604 KiB

race

#include<bits/stdc++.h>
using namespace std;

#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> os;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> oms;

// find_by_order to find the Kth element
// order_of_key to find number of elements smaller than x
// to erase from oms use order_of_key and than by its index find its iterator using find_by_order than erase it

#define MrRoamer() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define MOD 1000000007
#define MOD1 998244353
#define pb push_back
#define ppb pop_back
#define ff first
#define ss second
#define PI 3.141592653589793238462
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define chal(i,a,b) for(int i=a;i<=b;i++)
#define vi vector<int>
#define vvi vector<vector<int>>
#define prin(x) for(int i=0;i<x.size();i++)cout<<x[i]<<" ";cout<<endl;
#define take(x) for(int i=0;i<x.size();i++)cin>>x[i];

//---------------------------------------------------------------------------------------
typedef long long ll;
typedef unsigned long long ull;
typedef long double lld;

#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x << " "; _print(x); cerr << endl;
#else
#define debug(x)
#endif

void _print(ll t) { cerr << t; }
void _print(int t) { cerr << t; }
void _print(string t) { cerr << t; }
void _print(char t) { cerr << t; }
void _print(lld t) { cerr << t; }
void _print(double t) { cerr << t; }
void _print(ull t) { cerr << t; }

template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) { cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); cerr << "}"; }
template <class T> void _print(vector <T> v) { cerr << "[ "; for (T i : v) { _print(i); cerr << " "; } cerr << "]"; }
template <class T> void _print(set <T> v) { cerr << "[ "; for (T i : v) { _print(i); cerr << " "; } cerr << "]"; }
template <class T> void _print(multiset <T> v) { cerr << "[ "; for (T i : v) { _print(i); cerr << " "; } cerr << "]"; }
template <class T, class V> void _print(map <T, V> v) { cerr << "[ "; for (auto i : v) { _print(i); cerr << " "; } cerr << "]"; }

void printos(os v);
void printos(os v){ cerr << "[ "; for (ll i : v) { _print(i); cerr << " "; } cerr << "]"; cerr<<'\n';}
void printos(oms v);
void printos(oms v){ cerr << "[ "; for (ll i : v) { _print(i); cerr << " "; } cerr << "]"; cerr<<'\n';}

//--------------------------code toh yahan hai-----------------------------------



int ans=0;

void pre(int node,int p,vector<vector<pair<int,int>>> &adj,vi &dist,vi &dep)
{
    for(auto it:adj[node])
    {
        if(it.ff==p)continue;
        dist[it.ff]=dist[node]+it.ss;
        dep[it.ff]=dep[node]+1;
        pre(it.ff,node,adj,dist,dep);
    }
}


// void check(set<pair<int,int>>&st,pair<int,int> dist,pair<int,int>par)
// {
//     auto it=st.lower_bound({dist.ff-par.ff,-1});

//     if(it==st.end())return;
//     pair<int,int>p=
//     ans=min(ans,(dist.ff))
// }
void dfs(int node ,int p,vector<vector<pair<int,int>>> &adj,vector<set<pair<int,int>>>&have, vi &dist,vi &dep,int k)
{

    // debug(node)debug(have[node])
    for(auto it:adj[node])
    {
        if(it.ff==p)continue;
        dfs(it.ff,node,adj,have,dist,dep,k);

        if(have[it.ff].size()>have[node].size())
        {
            swap(have[it.ff],have[node]);
        }

        // auto t1=have[it.ff].lower_bound({k+dist[node],-1});
        // auto t2=have[node].lower_bound({k+dist[node],-1});
        // if(t1!=have[it.ff].end())
        // {
        //     ans=min(ans,(*t1).ss-dep[node]);
        // }
        // if(t2!=have[node].end())
        // {
        //     ans=min(ans,(*t2).ss-dep[node]);
        // }
        for(auto itr:have[it.ff])
        {
            auto item=have[node].lower_bound({k-(itr.ff-dist[node]),-1});
            debug(*item)
            if(item ==have[node].end())continue;
            if((*item).ff-dist[node]!=k-(itr.ff-dist[node]))continue;

            ans=min(ans,(*item).ss+itr.ss-2*dep[node]);
        }

        for(auto itr:have[it.ff])
        {
            have[node].insert(itr);
        }
    }

    have[node].insert({dist[node],dep[node]});
    debug(have[node])
    debug(node)
    debug(ans)
    auto t1=have[node].lower_bound({k+dist[node],-1});
    if(t1!=have[node].end())
    {
        ans=min(ans,(*t1).ss-dep[node]);
    }
    // int maxi=-1;

    // int bigchild=-1;

    // for(auto it:adj[node])
    // {
    //     if(have[it.ff].size()>maxi)
    //     {
    //         maxi=have[it.ff].size();
    //         bigchild=it.ff;
    //     }
    // }

    // if(bigchild==-1)
    // {
    //     have[node].insert({dist[node],dep[node]});
    //     return;
    // }


    // for(auto it:adj[node])
    // {
    //     if(it==p||it==bigchild)continue;



    // }
}

int best_path(int n,int k,int H[][2],int L[])
{
    vector<vector<pair<int,int>>>adj(n);
    vector<int>dist(n),dep(n);
    // {v,w}
    for(int i=0;i<n-1;i++)
    {
        adj[H[i][0]].pb({H[i][1],L[i]});
        adj[H[i][1]].pb({H[i][0],L[i]});
    }
    debug(adj)
    vector<set<pair<int,int>>>have(n);
    ans=1e18;
    pre(0,-1,adj,dist,dep);
    debug(dist)
    dfs(0,-1,adj,have,dist,dep,k);
    if(ans==1e18)return -1;
    return ans;
}

// void theProgram() {
//     int n,k;
//     cin>>n>>k;
//     int H[n-1][2];

//     for(int i=0;i<n-1;i++)
//     {
//         cin>>H[i][0]>>H[i][1];
//     }
//     int L[n+1];

//     for(int i=0;i<n-1;i++)cin>>L[i];
//     cout<<best_Path(n,k,H,L)<<endl;
// }

// signed main() {
//     MrRoamer();
//     // jaldi mat karna varna galti karega 
//     // constraints joi leje nakar penalty lagse
//     // zyada time lage toh switch the question
// #ifndef ONLINE_JUDGE
//     freopen("Error.txt", "w", stderr);
// #endif
//     int t=1;
//     // cin>>t;
//     while(t--){
//         theProgram();
//     }
//     return 0;
// }

Compilation message (stderr)

race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:182:9: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
  182 |     ans=1e18;
      |         ^~~~

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