# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
975097 |
2024-05-04T12:38:08 Z |
Amaarsaa |
Race (IOI11_race) |
C++11 |
|
505 ms |
41280 KB |
#include <iostream>
#include <algorithm>
#include <vector>
#include <chrono>
#include <cmath>
#pragma GCC optimize("Ofast")
#pragma GCC optimization ("unroll-loops")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef int_fast8_t int8;
typedef int_fast16_t int16;
typedef int_fast32_t int32;
typedef int_fast64_t int64;
typedef int_fast64_t ll;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> plll;
#define PB push_back
#define PF push_front
#define MP make_pair
#define FF first
#define SS second
namespace hash0 {
const double PI = acos(-1);
struct chash {
const uint64_t C = ll(2e18*PI)+71;
const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
inline ll operator()(ll x) const { return __builtin_bswap64((x ^ RANDOM) * C); }
inline ll operator()(pii p) const { return __builtin_bswap64((p.FF ^ RANDOM) * C) + p.SS; }
};
template<class K, class V>
using fast_map = gp_hash_table<K, V, chash>;
template<class K>
using fast_set = fast_map<K, null_type>;
}
using namespace hash0;
template<typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
return os << '(' << p.FF << ", " << p.SS << ')';
}
template<typename T1, typename T2>
ostream& operator<<(ostream& os, const fast_map<T1, T2>& s) {
os << '[';
if (s.size()) {
os << *s.begin();
for (auto i = ++s.begin(); i != s.end(); i++)
os << ", " << (*i);
}
return os << ']';
}
int N, K;
vector<pii> adj[200005];
int W[200005];
bool R[200005];
int dfs_w(int u, int p) {
W[u] = 1;
for (pii v : adj[u])
if (v.FF != p && !R[v.FF])
W[u] += dfs_w(v.FF, u);
return W[u];
}
int centroid(int u, int n, int p) {
for (pii v : adj[u])
if (v.FF != p && !R[v.FF])
if (W[v.FF] * 2 > n)
return centroid(v.FF, n, u);
return u;
}
int ans = 2000000011;
vector<pii> V;
void dfs_u(int u, int p, int d, int t) {
if (d > K || t > ans)
return;
V.PB(MP(d, t));
for (pii v : adj[u])
if (v.FF != p && !R[v.FF])
dfs_u(v.FF, u, d + v.SS, t + 1);
}
void init_cd(int u) {
u = centroid(u, dfs_w(u, -1), -1);
fast_map<int, int> M;
for (pii v : adj[u]) {
if (R[v.FF])
continue;
dfs_u(v.FF, u, v.SS, 1);
for (pii x : V) {
if (M.find(K - x.FF) != M.end())
ans = min(ans, M[K - x.FF] + x.SS);
else if (x.FF == K)
ans = min(ans, x.SS);
}
for (pii x : V) {
if (M.find(x.FF) == M.end())
M[x.FF] = x.SS;
else
M[x.FF] = min(M[x.FF], x.SS);
}
V.clear();
}
R[u] = 1;
for (pii v : adj[u])
if (!R[v.FF])
init_cd(v.FF);
}
int best_path(int n, int k, int h[][2], int l[]) {
N = n, K = k;
for (int i = 0; i < n - 1; i++) {
adj[h[i][0]].PB(MP(h[i][1], l[i]));
adj[h[i][1]].PB(MP(h[i][0], l[i]));
}
init_cd(0);
return ans == 2000000011 ? -1 : ans;
}
Compilation message
race.cpp:7: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
7 | #pragma GCC optimization ("unroll-loops")
|
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
9564 KB |
Output is correct |
2 |
Correct |
2 ms |
9564 KB |
Output is correct |
3 |
Correct |
3 ms |
9564 KB |
Output is correct |
4 |
Correct |
2 ms |
9564 KB |
Output is correct |
5 |
Correct |
2 ms |
9656 KB |
Output is correct |
6 |
Correct |
2 ms |
9564 KB |
Output is correct |
7 |
Correct |
2 ms |
9564 KB |
Output is correct |
8 |
Correct |
2 ms |
9564 KB |
Output is correct |
9 |
Correct |
2 ms |
9564 KB |
Output is correct |
10 |
Correct |
2 ms |
9564 KB |
Output is correct |
11 |
Correct |
2 ms |
9816 KB |
Output is correct |
12 |
Correct |
2 ms |
9564 KB |
Output is correct |
13 |
Correct |
2 ms |
9564 KB |
Output is correct |
14 |
Correct |
2 ms |
9816 KB |
Output is correct |
15 |
Correct |
2 ms |
9564 KB |
Output is correct |
16 |
Correct |
3 ms |
9564 KB |
Output is correct |
17 |
Correct |
2 ms |
9564 KB |
Output is correct |
18 |
Correct |
2 ms |
9564 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
9564 KB |
Output is correct |
2 |
Correct |
2 ms |
9564 KB |
Output is correct |
3 |
Correct |
3 ms |
9564 KB |
Output is correct |
4 |
Correct |
2 ms |
9564 KB |
Output is correct |
5 |
Correct |
2 ms |
9656 KB |
Output is correct |
6 |
Correct |
2 ms |
9564 KB |
Output is correct |
7 |
Correct |
2 ms |
9564 KB |
Output is correct |
8 |
Correct |
2 ms |
9564 KB |
Output is correct |
9 |
Correct |
2 ms |
9564 KB |
Output is correct |
10 |
Correct |
2 ms |
9564 KB |
Output is correct |
11 |
Correct |
2 ms |
9816 KB |
Output is correct |
12 |
Correct |
2 ms |
9564 KB |
Output is correct |
13 |
Correct |
2 ms |
9564 KB |
Output is correct |
14 |
Correct |
2 ms |
9816 KB |
Output is correct |
15 |
Correct |
2 ms |
9564 KB |
Output is correct |
16 |
Correct |
3 ms |
9564 KB |
Output is correct |
17 |
Correct |
2 ms |
9564 KB |
Output is correct |
18 |
Correct |
2 ms |
9564 KB |
Output is correct |
19 |
Correct |
2 ms |
9564 KB |
Output is correct |
20 |
Correct |
2 ms |
9764 KB |
Output is correct |
21 |
Correct |
3 ms |
9820 KB |
Output is correct |
22 |
Correct |
4 ms |
9652 KB |
Output is correct |
23 |
Correct |
3 ms |
9820 KB |
Output is correct |
24 |
Correct |
3 ms |
9816 KB |
Output is correct |
25 |
Correct |
4 ms |
9820 KB |
Output is correct |
26 |
Correct |
4 ms |
9820 KB |
Output is correct |
27 |
Correct |
3 ms |
9816 KB |
Output is correct |
28 |
Correct |
3 ms |
9816 KB |
Output is correct |
29 |
Correct |
3 ms |
9772 KB |
Output is correct |
30 |
Correct |
3 ms |
9820 KB |
Output is correct |
31 |
Correct |
3 ms |
9820 KB |
Output is correct |
32 |
Correct |
3 ms |
9816 KB |
Output is correct |
33 |
Correct |
3 ms |
9820 KB |
Output is correct |
34 |
Correct |
3 ms |
9564 KB |
Output is correct |
35 |
Correct |
3 ms |
9604 KB |
Output is correct |
36 |
Correct |
3 ms |
9820 KB |
Output is correct |
37 |
Correct |
3 ms |
9772 KB |
Output is correct |
38 |
Correct |
3 ms |
9816 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
9564 KB |
Output is correct |
2 |
Correct |
2 ms |
9564 KB |
Output is correct |
3 |
Correct |
3 ms |
9564 KB |
Output is correct |
4 |
Correct |
2 ms |
9564 KB |
Output is correct |
5 |
Correct |
2 ms |
9656 KB |
Output is correct |
6 |
Correct |
2 ms |
9564 KB |
Output is correct |
7 |
Correct |
2 ms |
9564 KB |
Output is correct |
8 |
Correct |
2 ms |
9564 KB |
Output is correct |
9 |
Correct |
2 ms |
9564 KB |
Output is correct |
10 |
Correct |
2 ms |
9564 KB |
Output is correct |
11 |
Correct |
2 ms |
9816 KB |
Output is correct |
12 |
Correct |
2 ms |
9564 KB |
Output is correct |
13 |
Correct |
2 ms |
9564 KB |
Output is correct |
14 |
Correct |
2 ms |
9816 KB |
Output is correct |
15 |
Correct |
2 ms |
9564 KB |
Output is correct |
16 |
Correct |
3 ms |
9564 KB |
Output is correct |
17 |
Correct |
2 ms |
9564 KB |
Output is correct |
18 |
Correct |
2 ms |
9564 KB |
Output is correct |
19 |
Correct |
92 ms |
15796 KB |
Output is correct |
20 |
Correct |
95 ms |
16720 KB |
Output is correct |
21 |
Correct |
96 ms |
16572 KB |
Output is correct |
22 |
Correct |
110 ms |
17348 KB |
Output is correct |
23 |
Correct |
56 ms |
17232 KB |
Output is correct |
24 |
Correct |
55 ms |
16988 KB |
Output is correct |
25 |
Correct |
100 ms |
17744 KB |
Output is correct |
26 |
Correct |
92 ms |
20092 KB |
Output is correct |
27 |
Correct |
171 ms |
20988 KB |
Output is correct |
28 |
Correct |
291 ms |
25920 KB |
Output is correct |
29 |
Correct |
218 ms |
26024 KB |
Output is correct |
30 |
Correct |
159 ms |
21464 KB |
Output is correct |
31 |
Correct |
144 ms |
21496 KB |
Output is correct |
32 |
Correct |
180 ms |
21444 KB |
Output is correct |
33 |
Correct |
197 ms |
20576 KB |
Output is correct |
34 |
Correct |
136 ms |
20816 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
9564 KB |
Output is correct |
2 |
Correct |
2 ms |
9564 KB |
Output is correct |
3 |
Correct |
3 ms |
9564 KB |
Output is correct |
4 |
Correct |
2 ms |
9564 KB |
Output is correct |
5 |
Correct |
2 ms |
9656 KB |
Output is correct |
6 |
Correct |
2 ms |
9564 KB |
Output is correct |
7 |
Correct |
2 ms |
9564 KB |
Output is correct |
8 |
Correct |
2 ms |
9564 KB |
Output is correct |
9 |
Correct |
2 ms |
9564 KB |
Output is correct |
10 |
Correct |
2 ms |
9564 KB |
Output is correct |
11 |
Correct |
2 ms |
9816 KB |
Output is correct |
12 |
Correct |
2 ms |
9564 KB |
Output is correct |
13 |
Correct |
2 ms |
9564 KB |
Output is correct |
14 |
Correct |
2 ms |
9816 KB |
Output is correct |
15 |
Correct |
2 ms |
9564 KB |
Output is correct |
16 |
Correct |
3 ms |
9564 KB |
Output is correct |
17 |
Correct |
2 ms |
9564 KB |
Output is correct |
18 |
Correct |
2 ms |
9564 KB |
Output is correct |
19 |
Correct |
2 ms |
9564 KB |
Output is correct |
20 |
Correct |
2 ms |
9764 KB |
Output is correct |
21 |
Correct |
3 ms |
9820 KB |
Output is correct |
22 |
Correct |
4 ms |
9652 KB |
Output is correct |
23 |
Correct |
3 ms |
9820 KB |
Output is correct |
24 |
Correct |
3 ms |
9816 KB |
Output is correct |
25 |
Correct |
4 ms |
9820 KB |
Output is correct |
26 |
Correct |
4 ms |
9820 KB |
Output is correct |
27 |
Correct |
3 ms |
9816 KB |
Output is correct |
28 |
Correct |
3 ms |
9816 KB |
Output is correct |
29 |
Correct |
3 ms |
9772 KB |
Output is correct |
30 |
Correct |
3 ms |
9820 KB |
Output is correct |
31 |
Correct |
3 ms |
9820 KB |
Output is correct |
32 |
Correct |
3 ms |
9816 KB |
Output is correct |
33 |
Correct |
3 ms |
9820 KB |
Output is correct |
34 |
Correct |
3 ms |
9564 KB |
Output is correct |
35 |
Correct |
3 ms |
9604 KB |
Output is correct |
36 |
Correct |
3 ms |
9820 KB |
Output is correct |
37 |
Correct |
3 ms |
9772 KB |
Output is correct |
38 |
Correct |
3 ms |
9816 KB |
Output is correct |
39 |
Correct |
92 ms |
15796 KB |
Output is correct |
40 |
Correct |
95 ms |
16720 KB |
Output is correct |
41 |
Correct |
96 ms |
16572 KB |
Output is correct |
42 |
Correct |
110 ms |
17348 KB |
Output is correct |
43 |
Correct |
56 ms |
17232 KB |
Output is correct |
44 |
Correct |
55 ms |
16988 KB |
Output is correct |
45 |
Correct |
100 ms |
17744 KB |
Output is correct |
46 |
Correct |
92 ms |
20092 KB |
Output is correct |
47 |
Correct |
171 ms |
20988 KB |
Output is correct |
48 |
Correct |
291 ms |
25920 KB |
Output is correct |
49 |
Correct |
218 ms |
26024 KB |
Output is correct |
50 |
Correct |
159 ms |
21464 KB |
Output is correct |
51 |
Correct |
144 ms |
21496 KB |
Output is correct |
52 |
Correct |
180 ms |
21444 KB |
Output is correct |
53 |
Correct |
197 ms |
20576 KB |
Output is correct |
54 |
Correct |
136 ms |
20816 KB |
Output is correct |
55 |
Correct |
12 ms |
10588 KB |
Output is correct |
56 |
Correct |
10 ms |
10076 KB |
Output is correct |
57 |
Correct |
84 ms |
16560 KB |
Output is correct |
58 |
Correct |
52 ms |
16804 KB |
Output is correct |
59 |
Correct |
143 ms |
27880 KB |
Output is correct |
60 |
Correct |
505 ms |
41280 KB |
Output is correct |
61 |
Correct |
161 ms |
21180 KB |
Output is correct |
62 |
Correct |
193 ms |
21840 KB |
Output is correct |
63 |
Correct |
197 ms |
21588 KB |
Output is correct |
64 |
Correct |
359 ms |
28860 KB |
Output is correct |
65 |
Correct |
140 ms |
22476 KB |
Output is correct |
66 |
Correct |
333 ms |
23932 KB |
Output is correct |
67 |
Correct |
88 ms |
23232 KB |
Output is correct |
68 |
Correct |
150 ms |
22376 KB |
Output is correct |
69 |
Correct |
141 ms |
20052 KB |
Output is correct |
70 |
Correct |
135 ms |
22356 KB |
Output is correct |