| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1099529 |
2024-10-11T14:22:40 Z |
Mr_Roamer |
Race (IOI11_race) |
C++17 |
|
37 ms |
604 KB |
#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
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;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
37 ms |
344 KB |
Output is correct |
| 2 |
Correct |
32 ms |
604 KB |
Output is correct |
| 3 |
Incorrect |
32 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
37 ms |
344 KB |
Output is correct |
| 2 |
Correct |
32 ms |
604 KB |
Output is correct |
| 3 |
Incorrect |
32 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
37 ms |
344 KB |
Output is correct |
| 2 |
Correct |
32 ms |
604 KB |
Output is correct |
| 3 |
Incorrect |
32 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
37 ms |
344 KB |
Output is correct |
| 2 |
Correct |
32 ms |
604 KB |
Output is correct |
| 3 |
Incorrect |
32 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
