| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 496077 | luanaamorim | Race (IOI11_race) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <queue>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <iomanip>
#include <map>
#include <cstring>
#include <set>
#include <stack>
#include <bitset>
#include <race.h>
#define ll long long
#define INF (1e9)
#define MAX (int) (2e2 + 5)
#define MOD 1000000007
#define par pair<int, int>
#define all(v) v.begin(), v.end()
#define sz(x) (int) ((x).size())
#define esq(x) (x<<1)
#define dir(x) ((x<<1)|1)
#define lsb(x) (x & -x)
#define W(x) cout << #x << ": " << x << endl
#define Wii(x) cout << x.first << ' ' << x.second << endl
#define _ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
int n, k, sub[MAX], vis[MAX], maior, h[MAX][2], l[MAX];
vector<par> grafo[MAX];
par f[MAX*10];
int dfs(int u, int p = 0)
{
if (vis[u]) return 0;
sub[u] = 1;
for (auto[v, w] : grafo[u])
if (v!=p) sub[u] += dfs(v, u);
return sub[u];
}
int centroid(int u, int p, int t)
{
for (auto[v, w] : grafo[u])
if (v!=p && !vis[v] && sub[v]>t/2) return centroid(v, u, t);
return u;
}
int query(int u, int p, int h, int d)
{
if (vis[u] || d>k) return INF;
maior = max(maior, h);
int resp = INF;
if (f[k-d].first) resp = f[k-d].second + h;
for (auto[v, w] : grafo[u])
if (v!=p) resp = min(resp, query(v, u, h+1, d+w));
return resp;
}
void update(int u, int p, int h, int d)
{
if (vis[u] || d>k) return;
if (f[d].first) f[d].second = min(f[d].second, h);
else f[d].second = h;
f[d].first=1;
for (auto[v, w] : grafo[u])
if (v!=p) update(v, u, h+1, d+w);
}
int solve(int u)
{
// dfs(u);
// int c = centroid(u, 0, sub[u]);
// vis[c] = 1;
// int resp = INF;
// for (int i = 0; i < MAX; i++)
// f[i] = {0, 0};
// f[0] = {1, 0};
// maior = 0;
// for (auto[v, w] : grafo[c])
// {
// resp = min(resp, query(v, 0, 1, w));
// update(v, 0, 1, w);
// }
// for (auto[v, w] : grafo[c])
// if (!vis[v]) resp = min(resp, solve(v));
// return resp;
int resp = INF;
for (int i = 1; i <= n; i++)
{
int tmp = INF;
vis[i] = 1;
for (int j = 0; j < MAX*10; j++)
f[j] = {0, 0};
f[0] = {1, 0};
for (auto[v, w] : grafo[i])
{
tmp = min(tmp, query(v, 0, 1, w));
update(v, 0, 1, w);
}
//cout <<
resp = min(resp, tmp);
}
return resp;
}
int best_path(int n, int k, int h[][2], int l[])
{_
for (int i = 1; i < n; i++)
{
grafo[h[i][0]+1].push_back({h[i][1]+1, l[i]});
grafo[h[i][1]+1].push_back({h[i][0]+1, l[i]});
}
int resp = solve(1);
return (resp==INF ? -1 : resp);
}
// int main()
// {
// cin >> n >> k;
// for (int i = 1; i < n; i++)
// {
// cin >> h[i][0] >> h[i][1] >> l[i];
// }
// cout << best_path(n, k, h, l) << endl;
// }
#include <iostream>
#include <queue>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <iomanip>
#include <map>
#include <cstring>
#include <set>
#include <stack>
#include <bitset>
#include <race.h>
#define ll long long
#define INF (1e9)
#define MAX (int) (2e2 + 5)
#define MOD 1000000007
#define par pair<int, int>
#define all(v) v.begin(), v.end()
#define sz(x) (int) ((x).size())
#define esq(x) (x<<1)
#define dir(x) ((x<<1)|1)
#define lsb(x) (x & -x)
#define W(x) cout << #x << ": " << x << endl
#define Wii(x) cout << x.first << ' ' << x.second << endl
#define _ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
int n, k, sub[MAX], vis[MAX], maior, h[MAX][2], l[MAX];
vector<par> grafo[MAX];
par f[MAX*10];
int dfs(int u, int p = 0)
{
if (vis[u]) return 0;
sub[u] = 1;
for (auto[v, w] : grafo[u])
if (v!=p) sub[u] += dfs(v, u);
return sub[u];
}
int centroid(int u, int p, int t)
{
for (auto[v, w] : grafo[u])
if (v!=p && !vis[v] && sub[v]>t/2) return centroid(v, u, t);
return u;
}
int query(int u, int p, int h, int d)
{
if (vis[u] || d>k) return INF;
maior = max(maior, h);
int resp = INF;
if (f[k-d].first) resp = f[k-d].second + h;
for (auto[v, w] : grafo[u])
if (v!=p) resp = min(resp, query(v, u, h+1, d+w));
return resp;
}
void update(int u, int p, int h, int d)
{
if (vis[u] || d>k) return;
if (f[d].first) f[d].second = min(f[d].second, h);
else f[d].second = h;
f[d].first=1;
for (auto[v, w] : grafo[u])
if (v!=p) update(v, u, h+1, d+w);
}
int solve(int u)
{
// dfs(u);
// int c = centroid(u, 0, sub[u]);
// vis[c] = 1;
// int resp = INF;
// for (int i = 0; i < MAX; i++)
// f[i] = {0, 0};
// f[0] = {1, 0};
// maior = 0;
// for (auto[v, w] : grafo[c])
// {
// resp = min(resp, query(v, 0, 1, w));
// update(v, 0, 1, w);
// }
// for (auto[v, w] : grafo[c])
// if (!vis[v]) resp = min(resp, solve(v));
// return resp;
int resp = INF;
for (int i = 1; i <= n; i++)
{
int tmp = INF;
vis[i] = 1;
for (int j = 0; j < MAX*10; j++)
f[j] = {0, 0};
f[0] = {1, 0};
for (auto[v, w] : grafo[i])
{
tmp = min(tmp, query(v, 0, 1, w));
update(v, 0, 1, w);
}
//cout <<
resp = min(resp, tmp);
}
return resp;
}
int best_path(int n, int k, int h[][2], int l[])
{_
for (int i = 1; i < n; i++)
{
grafo[h[i][0]+1].push_back({h[i][1]+1, l[i]});
grafo[h[i][1]+1].push_back({h[i][0]+1, l[i]});
}
int resp = solve(1);
return (resp==INF ? -1 : resp);
}
// int main()
// {
// cin >> n >> k;
// for (int i = 1; i < n; i++)
// {
// cin >> h[i][0] >> h[i][1] >> l[i];
// }
// cout << best_path(n, k, h, l) << endl;
// }