| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1003495 |
2024-06-20T11:55:46 Z |
_rain_ |
Race (IOI11_race) |
C++14 |
|
9 ms |
23896 KB |
#include "race.h"
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using ui64 = unsigned long long;
#define MASK(x) ((i64)(1) << (x))
#define BIT(mask , x) (((mask) >> (x)) & (1))
#define sz(x) (x).size()
#define all(x) (x).begin() , (x).end()
#define FOR(i ,a , b) for (int i = (a); i <= (b); ++i)
#define FORD(i , a , b) for (int i = (b); i >= (a); --i)
#define REP(i , a , b) for (int i = (a); i < (b); ++i)
#define REPD(i , a , b) for (int i = (b) - 1 ; i >= (a); --i)
template <class T>
void compress(vector<T> &a)
{
sort(a.begin() , a.end());
a.resize(unique(a.begin() , a.end()) - a.begin());
return;
}
template<class T>
void printArr(T& container , string separator = "" , string finish = "\n")
{
for (auto& item : container) cout << item << separator;
cout << finish;
}
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
template<class T>
bool maximize(T &a , T b) {if (a < b) return a = b , true; else return false;}
template<class T>
bool minimize(T &a , T b) {if (a > b) return a = b , true; else return false;}
template<class T>
T gcd(T x , T y) {while (y) swap(y , x %= y); return x;}
template<class T>
T lcm(T x , T y) {return (x * y) / gcd(x , y);}
const int maxn = 1e6;
int cnt[maxn + 2];
bool del[maxn + 2];
int sub[maxn + 2];
vector<pair<int,int>>g[maxn+2];
int n,k;
int find_centroid(int u , int p , int half)
{
for (auto& v : g[u])
{
if (del[v.first])continue;
if(v.first!=p&&sub[v.first]>half)return find_centroid(v.first,u,half);
}
return u;
}
void dfs_size(int u , int p)
{
sub[u] = 1;
for(auto&v:g[u])
if (v.first!=p&&!del[v.first])
{
dfs_size(v.first,u);
sub[u]+=sub[v.first];
}
return;
}
int maxh=0;
int answer=1e9+7;
void calc(int d,int h , int u , int p , int t)
{
maxh=max(maxh,h);
if (t)
minimize(cnt[h],d);
else
{
if(k-h>=0&&(i64)d+cnt[k-h]<=(int)1e9+7)
minimize(answer,d+cnt[k-h]);
}
for (auto& v : g[u])
if (!del[v.first]&&v.first!=p&&h+v.second<=k)
calc(d+1,h+v.second,v.first,u,t);
return;
}
void build(int u)
{
dfs_size(u,u);
u=find_centroid(u,u,sub[u]/2);
maxh=0;
del[u]=true;
cnt[0]=0;
for (auto& v : g[u])
{
if (del[v.first]) continue;
calc(1,v.second,v.first,u,0);
calc(1,v.second,v.first,u,1);
}
memset(cnt,0x3f,sizeof(int)*(maxh+2));
for(auto& v : g[u])
if (!del[v.first]) build(v.first);
return;
}
int best_path(int N, int K, int H[][2], int L[])
{
REP(i,0,n-1)
{
H[i][0]++;
H[i][1]++;
g[H[i][0]].push_back({H[i][1],L[i]});
g[H[i][1]].push_back({H[i][0],L[i]});
}
build(1);
N = (answer>=(int)1e9+7?-1:answer);
return N;
}
// int32_t main()
// {
// iostream::sync_with_stdio(false); cin.tie(0);
// const string name = "main";
// if (fopen((name + ".inp").c_str() , "r"))
// {
// (void)!freopen((name + ".inp").c_str() , "r" , stdin);
// (void)!freopen((name + ".out").c_str() , "w+", stdout);
// }
// memset(cnt,0x3f,sizeof cnt);
// cin>>n>>k;
// REP(i,1,n)
// {
// int u,v,h;cin>>u>>v>>h;
// ++u,++v;
// g[u].push_back({v,h});
// g[v].push_back({u,h});
// }
// cout<<(answer>=(int)1e9+7?-1:answer);
// }
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
23896 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
23896 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
23896 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
23896 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
