#include "factories.h"
#include <bits/stdc++.h>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define ll long long
#define ull unsigned long long
#define ld long double
#define vll vector<ll>
#define pll pair<ll, ll>
#define plll pair<pll, ll>
#define lpll pair<ll, pll>
#define FOR(i, start, stop) for(ll i = (start); i < (stop); i++)
#define fi(n) FOR(i, 0, n)
#define fj(n) FOR(j, 0, n)
#define fk(n) FOR(k, 0, n)
#define fio(n) FOR(i, 1, n)
#define fjo(n) FOR(j, 1, n)
#define fko(n) FOR(k, 1, n)
#define fiv(n) for (ll i = n-1; i >= 0; i--)
#define fjv(n) for (ll j = n-1; j >= 0; j--)
#define fkv(n) for (ll k = n-1; k >= 0; k--)
#define f first
#define s second
#define pb push_back
#define rt return
#define cn continue;
#define br break;
#define sz(x) ((ll)x.size())
#define all(queries) begin(queries),end(queries)
#define rall(queries) (queries).rbegin(),(queries).rend()
#define YESNO(flag) cout<<(flag ? "YES" : "NO") <<'\n';
#define dbg(...) {cerr << "\033[33m" << (#__VA_ARGS__) << ": "; dbg_vals(__VA_ARGS__); cerr << "\033[0m\n";}
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
template<class T> istream& operator>>(istream& in, vector<T>& x){for(T& i : x) in >> i; return in; }
template<class T, class TT> istream& operator>>(istream& in, pair<T, TT>& x){ in >> x.f >> x.s; return in; }
template<class T, class TT> ostream& operator<<(ostream& out, const pair<T, TT>& x){ out << x.f << ' ' << x.s; return out; }
template <typename Iter, typename=decltype(declval<Iter>().begin()), typename=enable_if_t<!is_convertible_v<Iter, string>>> ostream& operator<<(ostream& out, const Iter& x){ for (const auto& i : x) out << i << ' '; return out;}
template<typename T> void dbg_vals(T x){ cerr<< "\033[31m" << x << "\033[0m"; }
template<typename T, typename... Args> void dbg_vals(T x, Args... args){ dbg_vals(x); cerr << " | "; dbg_vals(args...); }
struct custom_hash { static uint64_t splitmix64(uint64_t x) {/*http://xorshift.di.unimi.it/splitmix64.c*/ x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31);} size_t operator()(uint64_t x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();return splitmix64(x + FIXED_RANDOM);}};
template<class T> using ll_umap = unordered_map<ll, T, custom_hash>;
using ll_uset = unordered_set<ll, custom_hash>;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
template<class T, class comp=less<T>> using ordered_set = __gnu_pbds::tree<T, __gnu_pbds::null_type, comp, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;
// find_by_order(k) - iterator on k's elements
// order_of_key(x) - number of elements, strictly less than x
template<class T> using min_pq = priority_queue<T, vector<T>, greater<T>>;
const ll MAXN = 512345;
const ll MOD = 1000'000'007;
const ld EPS = 1e-10;
const ll INF = (ll)(1ll<<60) + (ll)((1ll<<30)-1);
const ld PI = atanl(1)*4;
ll rll(ll r=numeric_limits<ll>::max(), ll l=0){ /*random long long*/ static mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); return uniform_int_distribution<ll>(l, r)(rng); }
template<typename F> auto time_measure(F f){ auto start = chrono::steady_clock::now(); f(); auto end = chrono::steady_clock::now(); return std::chrono::duration_cast<std::chrono::microseconds>(end - start).count(); }
array<ll, 3> extgcd(ll a, ll b) { if (!b) return {a, 1, 0}; auto [d, y, x] = extgcd(b, a % b); return {d, x, y - a/b * x}; } // {gcd, x, y} such that a*x + b*y = gcd(a, b)
ll gcd(ll x, ll y){ return __gcd(x, y); }
ll binpow(ll x, ll p, ll mod){ if (p < 0) return 0; x %= mod; ll ans = 1; while(p){ if (p&1) ans = (ans*x)%mod; x = (x*x)%mod; p >>= 1; } return ans; }
ll invmod(ll x, ll mod=MOD){ return binpow(x, mod-2, mod); }
ll sign(ll x){ if (x < 0) rt -1; rt !!x; }
void FREOPEN(string s){ freopen(string(s + ".in").c_str(), "r", stdin); freopen(string(s + ".out").c_str(), "w", stdout); }
template<class T, class TT> bool mineq(T& a, const TT& b){ if (b < a) {a = b; return true;} return false;}
template<class T, class TT> bool maxeq(T& a, const TT& b){ if (b > a) {a = b; return true;} return false;}
struct Edge{
int to, w;
Edge(int x = 0, int w=0):to(x), w(w){}
};
ll n, m, k, q;
ll ar[MAXN], cd[MAXN];
vector<Edge> gr[MAXN];
template<int N=MAXN>
class Calc_LCA{
constexpr static int log2_floor(int i) { return i ? __builtin_clz(1) - __builtin_clz(i) : -1; }
constexpr static int K = log2_floor(2*N)+1;
int pos[N], eul[2*N], lev[2*N], spt[K][2*N], t;
int merge(int a, int b){ return lev[a] < lev[b] ? a : b; }
int lca_h(int l, int r){
if (l > r) swap(l, r);
int i = log2_floor(r-l+1);
return merge(spt[i][l], spt[i][r-(1ll<<i)+1]);
}
public:
void build(const vector<Edge> gr[]){
function<void(int, int, int)> dfs = [&](int x, int p, int l){
eul[t] = x, pos[x] = t, lev[t] = l; t++;
for(Edge e : gr[x]) if (e.to != p){
dfs(e.to, x, l+1);
lev[t] = l, eul[t] = x; t++;
}
}; dfs(0, -1, 0);
for(int i = 0; i < t; i++) spt[0][i] = i;
for(int i = 1, k = log2_floor(t)+1; i < k; i++)
for(int j = 0; j + (1ll<<i) < t; j++)
spt[i][j] = merge(spt[i-1][j], spt[i-1][j + (1ll<<(i-1))]);
}
int lca(int a, int b){
a = pos[a], b = pos[b];
return eul[lca_h(a, b)];
}
int dist(int a, int b){
a = pos[a], b = pos[b];
return lev[a] + lev[b] - 2*lev[lca_h(a, b)];
}
}; Calc_LCA lca;
template<int N=MAXN>
struct Centroids_Tree{
int root, label[N], sizes[N];
vector<int> parent[N];
void build(const vector<Edge> gr[]){
function<int(int, int)> siz = [&](int x, int p){
sizes[x] = 1;
for(Edge e: gr[x]) if (e.to != p) sizes[x] += siz(e.to, x);
return sizes[x];
}; siz(0, -1);
fill(label, label+sizes[0], 0);
function<int(int, int, int)> dfs = [&](int x, int pc, int lab){
int n = sizes[x];
for (int ok = 1, p = -1; ok; ){
ok = 0;
for(Edge e : gr[x]){
if (e.to == p || label[e.to] || sizes[e.to] <= n/2) cn;
ok = 1, p = x;
sizes[x] = n - sizes[e.to];
x = e.to;
break;
}
sizes[x] = n;
}
if (pc == -1) pc = x, parent[x].clear();
parent[x] = parent[pc];
parent[x].push_back(x);
label[x] = lab;
for(Edge e: gr[x]) if (!label[e.to]) dfs(e.to, x, lab+1);
return x;
};
root = dfs(0, -1, 1);
}
}; Centroids_Tree ctree;
void dfs(int x, int p=-1){
for(Edge e : gr[x]){
if (e.to != p){
ar[e.to] = ar[x] + e.w;
dfs(e.to, x);
}
}
}
void solve(){
cin >> n;
fi(n-1){
ll a, b, c;
cin >> a >> b >> c;
a--, b--;
gr[a].pb(Edge(b, c));
gr[b].pb(Edge(a, c));
}
dfs(0);
ctree.build(gr);
lca.build(gr);
}
ll dist(int a, int b){
return ar[a] + ar[b] - 2*ar[lca.lca(a, b)];
};
void Init(int n, int A[], int B[], int D[]) {
fi(n-1){
gr[A[i]].pb(Edge(B[i], D[i]));
gr[B[i]].pb(Edge(A[i], D[i]));
}
dfs(0);
ctree.build(gr);
lca.build(gr);
fi(n) cd[i] = INF;
}
long long Query(int S, int X[], int T, int Y[]) {
fi(S){
for(auto cur : ctree.parent[X[i]]){
mineq(cd[cur], dist(X[i], cur));
}
}
ll ans = INF;
fi(T){
for(auto cur : ctree.parent[Y[i]]){
mineq(ans, cd[cur] + dist(Y[i], cur));
}
}
fi(S){
for(auto cur : ctree.parent[X[i]]){
cd[cur] = INF;
}
}
return ans;
}
Compilation message
factories.cpp: In function 'void FREOPEN(std::string)':
factories.cpp:73:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
73 | void FREOPEN(string s){ freopen(string(s + ".in").c_str(), "r", stdin); freopen(string(s + ".out").c_str(), "w", stdout); }
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
factories.cpp:73:80: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
73 | void FREOPEN(string s){ freopen(string(s + ".in").c_str(), "r", stdin); freopen(string(s + ".out").c_str(), "w", stdout); }
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
74332 KB |
Output is correct |
| 2 |
Correct |
393 ms |
91896 KB |
Output is correct |
| 3 |
Correct |
528 ms |
92140 KB |
Output is correct |
| 4 |
Correct |
536 ms |
91988 KB |
Output is correct |
| 5 |
Correct |
551 ms |
92640 KB |
Output is correct |
| 6 |
Correct |
205 ms |
91880 KB |
Output is correct |
| 7 |
Correct |
519 ms |
92244 KB |
Output is correct |
| 8 |
Correct |
541 ms |
92132 KB |
Output is correct |
| 9 |
Correct |
531 ms |
92652 KB |
Output is correct |
| 10 |
Correct |
203 ms |
89936 KB |
Output is correct |
| 11 |
Correct |
557 ms |
94704 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
74240 KB |
Output is correct |
| 2 |
Correct |
1977 ms |
225764 KB |
Output is correct |
| 3 |
Correct |
2387 ms |
252540 KB |
Output is correct |
| 4 |
Correct |
899 ms |
199072 KB |
Output is correct |
| 5 |
Correct |
3156 ms |
300108 KB |
Output is correct |
| 6 |
Correct |
2524 ms |
252728 KB |
Output is correct |
| 7 |
Correct |
1543 ms |
135360 KB |
Output is correct |
| 8 |
Correct |
378 ms |
126664 KB |
Output is correct |
| 9 |
Correct |
1543 ms |
141404 KB |
Output is correct |
| 10 |
Correct |
1603 ms |
135616 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
74332 KB |
Output is correct |
| 2 |
Correct |
393 ms |
91896 KB |
Output is correct |
| 3 |
Correct |
528 ms |
92140 KB |
Output is correct |
| 4 |
Correct |
536 ms |
91988 KB |
Output is correct |
| 5 |
Correct |
551 ms |
92640 KB |
Output is correct |
| 6 |
Correct |
205 ms |
91880 KB |
Output is correct |
| 7 |
Correct |
519 ms |
92244 KB |
Output is correct |
| 8 |
Correct |
541 ms |
92132 KB |
Output is correct |
| 9 |
Correct |
531 ms |
92652 KB |
Output is correct |
| 10 |
Correct |
203 ms |
89936 KB |
Output is correct |
| 11 |
Correct |
557 ms |
94704 KB |
Output is correct |
| 12 |
Correct |
13 ms |
74240 KB |
Output is correct |
| 13 |
Correct |
1977 ms |
225764 KB |
Output is correct |
| 14 |
Correct |
2387 ms |
252540 KB |
Output is correct |
| 15 |
Correct |
899 ms |
199072 KB |
Output is correct |
| 16 |
Correct |
3156 ms |
300108 KB |
Output is correct |
| 17 |
Correct |
2524 ms |
252728 KB |
Output is correct |
| 18 |
Correct |
1543 ms |
135360 KB |
Output is correct |
| 19 |
Correct |
378 ms |
126664 KB |
Output is correct |
| 20 |
Correct |
1543 ms |
141404 KB |
Output is correct |
| 21 |
Correct |
1603 ms |
135616 KB |
Output is correct |
| 22 |
Correct |
2981 ms |
227972 KB |
Output is correct |
| 23 |
Correct |
3168 ms |
231048 KB |
Output is correct |
| 24 |
Correct |
4050 ms |
248992 KB |
Output is correct |
| 25 |
Correct |
4030 ms |
251288 KB |
Output is correct |
| 26 |
Correct |
4172 ms |
249576 KB |
Output is correct |
| 27 |
Correct |
4546 ms |
288188 KB |
Output is correct |
| 28 |
Correct |
1246 ms |
197676 KB |
Output is correct |
| 29 |
Correct |
3937 ms |
248844 KB |
Output is correct |
| 30 |
Correct |
3883 ms |
248028 KB |
Output is correct |
| 31 |
Correct |
3936 ms |
249016 KB |
Output is correct |
| 32 |
Correct |
1578 ms |
138924 KB |
Output is correct |
| 33 |
Correct |
446 ms |
123076 KB |
Output is correct |
| 34 |
Correct |
1291 ms |
126188 KB |
Output is correct |
| 35 |
Correct |
1137 ms |
126416 KB |
Output is correct |
| 36 |
Correct |
1450 ms |
130716 KB |
Output is correct |
| 37 |
Correct |
1584 ms |
130784 KB |
Output is correct |
