| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 537138 |
2022-03-14T15:38:33 Z |
BossBobster |
Race (IOI11_race) |
C++17 |
|
2 ms |
4948 KB |
#include <iostream>
#include <string.h>
#include <random>
#include <fstream>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <iomanip>
#include <algorithm>
#include <math.h>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <complex>
#include <valarray>
using namespace std;
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef pair<int, int> pii;
typedef pair<int, string> pis;
typedef pair<int, short> pish;
typedef pair<string, string> pss;
typedef pair<int, char> pic;
typedef pair<pii, int> piii;
typedef pair<double, double> pdd;
typedef pair<float, float> pff;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<ll, ll> pll;
typedef pair<pll, ll> plll;
typedef pair<pll, ld> plld;
typedef pair<int, ll> pil;
typedef pair<ull, ull> pull;
typedef pair<ld, ld> pld;
typedef complex<double> cd;
//#define max(n, m) ((n>m)?n:m)
//#define min(n, m) ((n<m)?n:m)
#define f first
#define s second
#define input() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define eps 1e-9
//#define cin fin
vector<pii> adj[200010];
int n, k, a, b, root;
int sz[200010];
int p[200010];
bitset<200010> vis;
int dfs1(int cur, int par)
{
sz[cur] = 1;
for(auto nx : adj[cur])
if(nx.f != par && !vis[nx.f])
sz[cur] += dfs1(nx.f, cur);
return sz[cur];
}
int dfs2(int cur, int par, int n)
{
for(auto nx : adj[cur])
if(nx.f != par && sz[nx.f] > n/2 && !vis[nx.f])
return dfs2(nx.f, cur, n);
return cur;
}
int mx;
int ans = 2000000000;
unordered_map<int, int> cnt;
void dfs3(int cur, int par, int d, int num)
{
if(d > k) return;
mx = max(mx, d);
if(cnt[k-d] != 0 || k-d == 0)
ans = min(ans, num+cnt[k-d]);
for(auto nx : adj[cur])
if(nx.f != par && !vis[nx.f])
dfs3(nx.f, cur, d+nx.s, num+1);
}
void dfs4(int cur, int par, int d, int num)
{
if(d > k) return;
mx = max(mx, d);
if(cnt[d] == 0) cnt[d] = 2000000000;
cnt[d] = min(cnt[d], num);
for(auto nx : adj[cur])
if(nx.f != par && !vis[nx.f])
dfs4(nx.f, cur, d+nx.s, num+1);
}
void make(int cur, int par)
{
int cent = dfs2(cur, par, dfs1(cur, par));
vis[cent] = 1;
mx = 0;
for(auto it : adj[cent])
if(!vis[it.f])
dfs3(it.f, cent, it.s, 1), dfs4(it.f, cent, it.s, 1);
cnt.clear();
for(auto it : adj[cent])
if(!vis[it.f])
make(it.f, cent);
}
int best_path(int n2, int k2, int edges[][2], int nums[])
{
for(int i = 0; i < n-1; i ++)
adj[edges[i][0]].push_back({edges[i][1], nums[i]}), adj[edges[i][1]].push_back({edges[i][0], nums[i]});
k = k2; n = n2;
make(0, -1);
return ((ans==2000000000)?-1:ans);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
