| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1093107 |
2024-09-26T00:47:39 Z |
anhthi |
Race (IOI11_race) |
C++14 |
|
2 ms |
12636 KB |
#include <bits/stdc++.h>
#include "race.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define mp(x, y) make_pair(x, y)
#define sz(v) ((int) (v).size())
#define all(v) (v).begin(), (v).end()
#define MASK(i) (1LL << (i))
#define BIT(x, y) (((x) >> (y)) & 1)
#define pb push_back
#define max_rng *max_element
#define min_rng *min_element
#define rep(i, n) for(int i = 1, _n = (n); i <= _n; ++i)
#define forn(i, a, b) for(int i = (a), _b = (b); i <= _b; ++i)
#define ford(i, a, b) for(int i = (a), _b = (b); i >= _b; --i)
template <class X, class Y>
inline bool maximize(X &x, Y y) {
return (x < y ? x = y, true : false);
}
template <class X, class Y>
inline bool minimize(X &x, Y y) {
return (x > y ? x = y, true : false);
}
template <class X>
inline void compress(vector<X> &a) {
sort(all(a));
a.resize(unique(all(a)) - a.begin());
}
int ctz(ll x) { return __builtin_ctzll(x); }
int lg(ll x) { return 63 - __builtin_clzll(x); }
int popcount(ll x) { return __builtin_popcount(x); }
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) {
return l + abs((ll) rng()) % (r - l + 1);
}
const ll oo = (ll) 1e17;
const int inf = (ll) 2e9 + 7, mod = (ll) 1e9 + 7;
const int mxn = 3e5 + 5, mxm = 3e2 + 5;
const int LG = 18, BASE = 311, BLOCK = 350;
void add(int &x, int y) { x += y; if (x >= mod) x -= mod; }
void sub(int &x, int y) { x -= y; if (x < 0) x += mod; }
int n, k;
ll w[mxn];
vector<pair<int, int>> g[mxn];
bool del[mxn];
int childs[mxn];
int getSz(int u, int p) {
childs[u] = 1;
for (auto &[v, i] : g[u]) if (v != p && !del[v]) {
childs[u] += getSz(v, u);
}
return childs[u];
}
int getCen(int u, int p, int sz) {
for (auto &[v, i] : g[u]) if (v != p && !del[v]) {
if (2 * childs[v] > sz) return getCen(v, u, sz);
}
return u;
}
int ans = inf;
map<ll, int> mp;
void dfs(int u, int p, bool flag, ll dist, int d = 1) {
if (dist > k) return;
if (flag) {
if (mp.find(k - dist) != mp.end()) {
minimize(ans, mp[k - dist] + d);
}
}
else {
if (mp.find(dist) == mp.end())
mp[dist] = d;
else minimize(mp[dist], d);
}
for (auto &[v, i] : g[u]) if (v != p && !del[v])
dfs(v, u, flag, dist + w[i], d + 1);
return;
}
void solve(int root) {
mp.clear();
mp[0] = 0;
for (auto &[v, i] : g[root]) if (v != root && !del[v]) {
dfs(v, root, 0, w[i]);
dfs(v, root, 1, w[i]);
}
return;
}
void dnc(int u) {
int sz = getSz(u, 0);
int cen = getCen(u, 0, cen);
solve(cen);
del[cen] = true;
for (auto &[v, i] : g[cen]) if (!del[v])
dnc(v);
}
int best_path(int N, int K, int H[][2], int L[]) {
n = N; k = K;
forn(i, 0, n - 2) {
int u = H[i][0];
int v = H[i][1];
u++; v++;
g[u].pb(mp(v, i));
g[v].pb(mp(u, i));
}
forn(i, 0, n - 2) w[i] = L[i];
dnc(1);
return (ans == inf ? -1 : ans);
}
//int main(void) {
//
// ios_base::sync_with_stdio(0);
// cin.tie(0); cout.tie(0);
//
// #define TASK "cquery"
// if (fopen(TASK".inp", "r")) {
// freopen(TASK".inp", "r", stdin);
// freopen(TASK".out", "w", stdout);
// }
//
// int a[][2] = {{0, 1}, {1, 2}, {1, 3}};
// int b[] = {1, 2, 4};
// best_path(4, 3, a, b);
//
// return 0;
//}
Compilation message
race.cpp: In function 'int getSz(int, int)':
race.cpp:63:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
63 | for (auto &[v, i] : g[u]) if (v != p && !del[v]) {
| ^
race.cpp: In function 'int getCen(int, int, int)':
race.cpp:70:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
70 | for (auto &[v, i] : g[u]) if (v != p && !del[v]) {
| ^
race.cpp: In function 'void dfs(int, int, bool, long long int, int)':
race.cpp:92:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
92 | for (auto &[v, i] : g[u]) if (v != p && !del[v])
| ^
race.cpp: In function 'void solve(int)':
race.cpp:102:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
102 | for (auto &[v, i] : g[root]) if (v != root && !del[v]) {
| ^
race.cpp: In function 'void dnc(int)':
race.cpp:117:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
117 | for (auto &[v, i] : g[cen]) if (!del[v])
| ^
race.cpp:111:9: warning: unused variable 'sz' [-Wunused-variable]
111 | int sz = getSz(u, 0);
| ^~
race.cpp:112:21: warning: 'cen' is used uninitialized in this function [-Wuninitialized]
112 | int cen = getCen(u, 0, cen);
| ~~~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
12636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
12636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
12636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
12636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
