| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 593485 |
2022-07-11T08:59:52 Z |
nguyentu |
Race (IOI11_race) |
C++14 |
|
31 ms |
83284 KB |
#include "race.h"
#include <bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
#define ii pair<ll , ll>
#define iv pair<ii , ii>
#define iii pair<ll , ii>
#define fi first
#define se second
#define ll long long
const ll inf = 1e18 + 7;
const ll MAX_N = 2e5 + 7;
const ll MOD = 1e9 + 7;
const ll MAX_VAL = 1e7 + 7;
map<ll , ll> cnt;
map<ll , ll> tmp;
ll n , k;
vector<ii> adj[MAX_N];
bool check[MAX_N];
ll f[MAX_N] , dp[MAX_N] , g[MAX_N];
ll lowest_K[MAX_VAL];
ll low[MAX_VAL];
void DFS(ll u , ll father) {
f[u] = 1;
for (auto edge : adj[u]) {
ll v = edge.fi;
if (v != father && !check[v]) {
DFS(v , u);
f[u] += f[v];
}
}
return;
}
ll find_centroid(ll u , ll father , ll root){
for (auto edge : adj[u]) {
ll v = edge.fi;
if (!check[v] && v != father && 2*f[v] >= f[root]) {
return find_centroid(v , u , root);
}
}
return u;
}
void DFS1(ll u , ll father) {
if (dp[u] <= k && g[u] < low[dp[u]]) {
low[dp[u]] = g[u];
cnt[dp[u]] = 1;
}
else if (dp[u] <= k && g[u] == low[dp[u]]) {
cnt[dp[u]]++;
}
for (auto edge : adj[u]) {
ll v = edge.fi , w = edge.se;
if (v != father && !check[v]) {
dp[v] = dp[u] + w;
g[v] = g[u] + 1;
DFS1(v , u);
}
}
return;
}
void DFS2(ll u , ll father) {
if (dp[u] <= k && g[u] == low[dp[u]]) {
tmp[dp[u]]++;
}
for (auto edge : adj[u]) {
ll v = edge.fi;
if (v != father && !check[v]) {
DFS2(v , u);
}
}
}
void centroid(ll u , ll father) {
DFS(u , u);
u = find_centroid(u , u , u);
cnt.clear();
dp[u] = 0;
g[u] = 0;
DFS1(u , u);
for (auto it : cnt) {
ll x = k - it.fi;
if (x < 0 || it.fi > k || x > k) continue;
ll val = it.se;
if (it.fi == x) {
ll tmp1 = low[it.fi];
if (tmp1 != inf) {
ll num = 2*tmp1;
lowest_K[num] += val*(val - 1);
}
}
else {
ll tmp1 = low[it.fi] ,tmp2 = low[x];
if (tmp1 != inf && tmp2 != inf) {
ll num = tmp1 + tmp2;
lowest_K[num] += val*cnt[x];
}
}
}
check[u] = 1;
for (auto edge : adj[u]) {
ll v = edge.fi;
if (v != father && !check[v]) {
tmp.clear();
DFS2(v , v);
for (auto it : tmp) {
ll x = k - it.fi;
if (x < 0 || it.fi > k || x > k) continue;
ll val = it.se;
if (it.fi == x) {
ll tmp1 = low[it.fi];
if (tmp1 != inf) {
ll num = 2*tmp1;
lowest_K[num] -= val*(val - 1);
}
}
else {
ll tmp1 = low[it.fi] ,tmp2 = low[x];
if (tmp1 != inf && tmp2 != inf) {
ll num = tmp1 + tmp2;
lowest_K[num] -= val*tmp[x];
}
}
}
}
}
for (auto edge : adj[u]) {
ll v = edge.fi;
if (v != father && !check[v]) {
centroid(v , u);
}
}
}
int best_path(int N, int K, int H[][2], int L[]){
n = N , k = K;
for (ll i = 0 ; i < (n - 1) ; i++) {
adj[H[i][0] + 1].push_back(ii(H[i][1] + 1 , L[i]));
adj[H[i][1]+1].push_back(ii(H[i][0]+1 , L[i]));
}
for (ll i = 0 ; i < MAX_VAL ; i++) {
low[i] = inf;
}
centroid(1 , -1);
for (ll i = 0 ; i < MAX_VAL ; i++) {
if (lowest_K[i]) {
return i;
}
}
return -1;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
83284 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
83284 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
83284 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
83284 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
