#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;
map<ll, ll> dist[500005];
ll best[500005];
struct centroid {
vector<pair<ll, ll>> edges[500005];
bool vis[500005];
ll par[500005];
ll sz[500005];
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][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]);
if (n < 1000) 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[]) {
assert(n <= 5000);
memset(best, 1, sizeof(best));
for (ll i = 0; i < n - 1; i++) {
cd.edge(aa[i], bb[i], dd[i]);
}
cd.init_centroid();
}
void reset(ll v) {
ll c = v;
do {
best[c] = 1e17;
c = cd.par[c];
} while (c != -1);
}
void push(ll v) {
ll c = v;
do {
best[c] = min(best[c], dist[c][v]);
c = cd.par[c];
} while (c != -1);
}
void pull(ll v) {
ll c = v;
do {
ans = min(ans, best[c] + dist[c][v]);
c = cd.par[c];
} while (c != -1);
}
ll Query(int s, int x[], int t, int y[]) {
if (n > 5000) exit(0);
// cout << s << " " << t << endl;
for (ll i = 0; i < s; i++) reset(x[i]);
for (ll i = 0; i < t; i++) reset(y[i]);
for (ll i = 0; i < s; i++) push(x[i]);
ans = 1e17;
for (ll i = 0; i < t; i++) pull(y[i]);
return ans;
}
#ifdef galen_colin_local
void solve(int tc = 0) {
// cin >> n >> q;
n = 5000, q = 0;
for (ll i = 0; i < n - 1; i++) {
// cin >> a[i] >> b[i] >> c[i];
a[i] = rng() % (i + 1), b[i] = i + 1, c[i] = 1e9;
}
Init(n, a, b, c);
for (ll i = 0; i < q; i++) {
ll s, t;
cin >> s >> t;
for (ll j = 0; j < s; j++) cin >> a[j];
for (ll j = 0; j < t; j++) cin >> b[j];
cout << Query(s, a, t, b) << '\n';
}
}
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 |
47 ms |
39916 KB |
Output is correct |
| 2 |
Correct |
1817 ms |
50240 KB |
Output is correct |
| 3 |
Correct |
2869 ms |
50932 KB |
Output is correct |
| 4 |
Correct |
2716 ms |
50924 KB |
Output is correct |
| 5 |
Correct |
3532 ms |
51784 KB |
Output is correct |
| 6 |
Correct |
556 ms |
48492 KB |
Output is correct |
| 7 |
Correct |
2892 ms |
50924 KB |
Output is correct |
| 8 |
Correct |
2902 ms |
51064 KB |
Output is correct |
| 9 |
Correct |
3546 ms |
52076 KB |
Output is correct |
| 10 |
Correct |
552 ms |
48492 KB |
Output is correct |
| 11 |
Correct |
2746 ms |
51048 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
39788 KB |
Output is correct |
| 2 |
Runtime error |
427 ms |
94160 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
47 ms |
39916 KB |
Output is correct |
| 2 |
Correct |
1817 ms |
50240 KB |
Output is correct |
| 3 |
Correct |
2869 ms |
50932 KB |
Output is correct |
| 4 |
Correct |
2716 ms |
50924 KB |
Output is correct |
| 5 |
Correct |
3532 ms |
51784 KB |
Output is correct |
| 6 |
Correct |
556 ms |
48492 KB |
Output is correct |
| 7 |
Correct |
2892 ms |
50924 KB |
Output is correct |
| 8 |
Correct |
2902 ms |
51064 KB |
Output is correct |
| 9 |
Correct |
3546 ms |
52076 KB |
Output is correct |
| 10 |
Correct |
552 ms |
48492 KB |
Output is correct |
| 11 |
Correct |
2746 ms |
51048 KB |
Output is correct |
| 12 |
Correct |
29 ms |
39788 KB |
Output is correct |
| 13 |
Runtime error |
427 ms |
94160 KB |
Execution killed with signal 6 |
| 14 |
Halted |
0 ms |
0 KB |
- |
