| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1112707 |
2024-11-14T16:19:20 Z |
hainam2k9 |
Race (IOI11_race) |
C++17 |
|
2 ms |
8784 KB |
#include <bits/stdc++.h>
#include <race.h>
#define tt cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(0)
#define fo freopen((NAME+".INP").c_str(), "r", stdin), freopen((NAME+".OUT").c_str(), "w", stdout)
#define ll long long
#define ull unsigned long long
#define i128 __int128
#define db long double
#define sz(a) ((int)(a).size())
#define pb emplace_back
#define pf emplace_front
#define pob pop_back
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define ins emplace
using namespace std;
const int MOD = 1e9+7, MAXN = 2e5+5;
const string NAME = "";
int n,k,rs=MAXN,sz[MAXN];
bool del[MAXN];
vector<pair<int,int>> adj[MAXN];
map<ll,int> cnt;
void GetSize(int u, int par){
sz[u]=1;
for(pair<int,int> p : adj[u])
if(p.fi!=par&&!del[p.fi]) GetSize(p.fi,u), sz[u]+=sz[p.fi];
}
int Centroid(int u, int par){
for(pair<int,int> p : adj[u])
if(p.fi!=par&&!del[p.fi]&&sz[p.fi]>n>>1) return Centroid(p.fi,u);
return u;
}
void dfs(int u, int par, bool type, int cur, ll len){
if(k<len) return;
if(type==0&&cnt.find(k-len)!=cnt.end()) rs=min(rs,cnt[k-len]+cur);
else if(len==k) rs=min(rs,cur);
else cnt[len]= !cnt[len] ? cur : min(cnt[len],cur);
for(pair<int,int> p : adj[u])
if(p.fi!=par) dfs(p.fi,u,type,cur+1,len+p.se);
}
void CentroidDecomposition(int u){
GetSize(u,0), n=sz[u];
int root=Centroid(u,0);
cnt.clear();
for(pair<int,int> p : adj[root])
if(!del[p.fi]) dfs(p.fi,root,0,1,p.se), dfs(p.fi,root,1,1,p.se);
del[root]=1;
for(pair<int,int> p : adj[root])
if(!del[p.fi]) CentroidDecomposition(p.fi);
}
int best_path(int N, int K, int h[][2], int l[]){
n=N, k=K;
for(int i = 1; i<n; ++i)
adj[h[i-1][0]+1].pb(h[i-1][1]+1,l[i-1]), adj[h[i-1][1]+1].pb(h[i-1][0]+1,l[i-1]);
CentroidDecomposition(1);
return rs==MAXN ? -1 : rs;
}
//int main()
//{
// tt;
// if(fopen((NAME + ".INP").c_str(), "r")) fo;
// cin >> n >> k;
// int h[n][2], l[n];
// for(int i = 0; i<n-1; ++i)
// cin >> h[i][0] >> h[i][1];
// for(int i = 0; i<n-1; ++i)
// cin >> l[i];
// cout << best_path(n,k,h,l);
//}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8784 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8784 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8784 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8784 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
