#include "bits/stdc++.h"
#ifndef galen_colin_local
#include "factories.h"
#endif
using namespace std;
/*
find my code templates at https://github.com/galencolin/cp-templates
also maybe subscribe please thanks
*/
#define send {ios_base::sync_with_stdio(false);}
#define help {cin.tie(NULL);}
#define f first
#define s second
#define getunique(v) {sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());}
typedef long long ll;
typedef long double lld;
typedef unsigned long long ull;
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v);
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; }
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v) {
cout << "["; for(int i = 0; i < v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]";
}
template<typename A, typename B> istream& operator>>(istream& cin, pair<A, B> &p) {
cin >> p.first;
return cin >> p.second;
}
mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
// mt19937_64 rng(61378913);
/* usage - just do rng() */
void usaco(string filename) {
// #pragma message("be careful, freopen may be wrong")
freopen((filename + ".in").c_str(), "r", stdin);
freopen((filename + ".out").c_str(), "w", stdout);
}
// #include <atcoder/all>
// using namespace atcoder;
const lld pi = 3.14159265358979323846;
const ll mod = 1000000007;
// const ll mod = 998244353;
// ll mod;
ll n, m, q, k, l, r, x, y, z;
const ll template_array_size = 1e6 + 14742;
int a[template_array_size];
int b[template_array_size];
int c[template_array_size];
string s, t;
ll ans = 0;
vector<pair<int, ll>> dist[500005];
ll best[500005];
struct centroid {
vector<vector<pair<ll, ll>> > edges;
vector<bool> vis;
vector<int> par;
vector<int> sz;
int n;
void init(int s) {
n = s;
edges = vector<vector<pair<ll, ll>> >(n, vector<pair<ll, ll>>());
vis = vector<bool>(n, 0);
par = vector<int>(n);
sz = vector<int>(n);
}
void edge(ll a, ll b, ll c) {
edges[a].push_back({b, c});
edges[b].push_back({a, c});
}
int find_size(int v, int p = -1) {
if (vis[v]) return 0;
sz[v] = 1;
for (pair<ll, ll> x: edges[v]) {
if (x.f != p) {
sz[v] += find_size(x.f, v);
}
}
return sz[v];
}
int find_centroid(int v, int p, int n) {
for (pair<ll, ll> x: edges[v]) {
if (x.f != p) {
if (!vis[x.f] && sz[x.f] > n / 2) {
return find_centroid(x.f, v, n);
}
}
}
return v;
}
void set_dists(ll v, ll p, ll d, ll c) {
dist[c].push_back({v, d});
for (pair<ll, ll> x: edges[v]) {
if (x.f != p && !vis[x.f]) {
set_dists(x.f, v, d + x.s, c);
}
}
}
void init_centroid(int v = 0, int p = -1) {
find_size(v);
int c = find_centroid(v, -1, sz[v]);
set_dists(c, -1, 0, c);
vis[c] = true;
par[c] = p;
for (pair<ll, ll> x: edges[c]) {
if (!vis[x.f]) {
init_centroid(x.f, c);
}
}
}
};
centroid cd;
void Init(int n, int aa[], int bb[], int dd[]) {
cd.init(n);
memset(best, 1, sizeof(best));
for (ll i = 0; i < n - 1; i++) {
cd.edge(aa[i], bb[i], dd[i]);
}
cd.init_centroid();
for (ll i = 0; i < n; i++) sort(dist[i].begin(), dist[i].end());
}
ll dists(int c, int v) {
int l = 0, r = dist[c].size();
while (l < r) {
int m = (l + r) / 2;
if (dist[c][m].f >= v) r = m;
else l = m + 1;
}
return dist[c][l].s;
}
void reset(int v) {
int c = v;
do {
best[c] = 1e17;
c = cd.par[c];
} while (c != -1);
}
void push(int v) {
int c = v;
do {
best[c] = min(best[c], dists(c, v));
c = cd.par[c];
} while (c != -1);
}
void pull(int v) {
int c = v;
do {
ans = min(ans, best[c] + dists(c, v));
c = cd.par[c];
} while (c != -1);
}
ll Query(int s, int x[], int t, int y[]) {
// cout << s << " " << t << endl;
for (int i = 0; i < s; i++) reset(x[i]);
for (int i = 0; i < t; i++) reset(y[i]);
for (int i = 0; i < s; i++) push(x[i]);
ans = 1e17;
for (int i = 0; i < t; i++) pull(y[i]);
return ans;
}
#ifdef galen_colin_local
void solve(int tc = 0) {
// cin >> n >> q;
ll n = 500000, q = 10000;
for (ll i = 0; i < n - 1; i++) {
a[i] = i, b[i] = i + 1, c[i] = rng() % 1000000000;
// cin >> a[i] >> b[i] >> c[i];
}
Init(n, a, b, c);
for (ll i = 0; i < q; i++) {
// ll s, t;
// cin >> s >> t;
ll s = 10, t = 10;
// for (ll j = 0; j < s; j++) cin >> a[j];
// for (ll j = 0; j < t; j++) cin >> b[j];
for (ll j = 0; j < s; j++) a[j] = rng() % n;
for (ll j = 0; j < t; j++) b[j] = rng() % n;
// cout << Query(s, a, t, b) << '\n';
Query(s, a, t, b);
}
}
int main() {
#ifdef galen_colin_local
auto begin = std::chrono::high_resolution_clock::now();
#endif
send help
#ifndef galen_colin_local
// usaco("code");
#endif
// usaco("cowland");
// freopen("tc.cpp", "r", stdin);
// freopen("tc2.cpp", "w", stdout);
cout << setprecision(15) << fixed;
int tc = 1;
// cin >> tc;
for (int t = 0; t < tc; t++) solve(t);
#ifdef galen_colin_local
auto end = std::chrono::high_resolution_clock::now();
cerr << setprecision(4) << fixed;
cerr << "Execution time: " << std::chrono::duration_cast<std::chrono::duration<double>>(end - begin).count() << " seconds" << endl;
#endif
}
#endif
Compilation message
factories.cpp: In function 'void usaco(std::string)':
factories.cpp:39:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
39 | freopen((filename + ".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
factories.cpp:40:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
40 | freopen((filename + ".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
16364 KB |
Output is correct |
| 2 |
Correct |
1206 ms |
25196 KB |
Output is correct |
| 3 |
Correct |
1691 ms |
25580 KB |
Output is correct |
| 4 |
Correct |
1684 ms |
25724 KB |
Output is correct |
| 5 |
Correct |
1983 ms |
26476 KB |
Output is correct |
| 6 |
Correct |
482 ms |
24684 KB |
Output is correct |
| 7 |
Correct |
1677 ms |
25708 KB |
Output is correct |
| 8 |
Correct |
1769 ms |
25708 KB |
Output is correct |
| 9 |
Correct |
2007 ms |
26284 KB |
Output is correct |
| 10 |
Correct |
477 ms |
24684 KB |
Output is correct |
| 11 |
Correct |
1672 ms |
26092 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
16236 KB |
Output is correct |
| 2 |
Correct |
7041 ms |
176364 KB |
Output is correct |
| 3 |
Execution timed out |
8103 ms |
222188 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
16364 KB |
Output is correct |
| 2 |
Correct |
1206 ms |
25196 KB |
Output is correct |
| 3 |
Correct |
1691 ms |
25580 KB |
Output is correct |
| 4 |
Correct |
1684 ms |
25724 KB |
Output is correct |
| 5 |
Correct |
1983 ms |
26476 KB |
Output is correct |
| 6 |
Correct |
482 ms |
24684 KB |
Output is correct |
| 7 |
Correct |
1677 ms |
25708 KB |
Output is correct |
| 8 |
Correct |
1769 ms |
25708 KB |
Output is correct |
| 9 |
Correct |
2007 ms |
26284 KB |
Output is correct |
| 10 |
Correct |
477 ms |
24684 KB |
Output is correct |
| 11 |
Correct |
1672 ms |
26092 KB |
Output is correct |
| 12 |
Correct |
15 ms |
16236 KB |
Output is correct |
| 13 |
Correct |
7041 ms |
176364 KB |
Output is correct |
| 14 |
Execution timed out |
8103 ms |
222188 KB |
Time limit exceeded |
| 15 |
Halted |
0 ms |
0 KB |
- |
