#include "factories.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ll> vll;
typedef pair<long long, long long> pll;
typedef pair<char, ll> ci;
typedef pair<string, ll> si;
typedef long double ld;
typedef vector<ll> vi;
typedef vector<string> vs;
#define pb push_back
#define fi first
#define se second
#define whole(v) v.begin(), v.end()
#define rwhole(v) v.rbegin(), v.rend()
const ll inf = 10000000000000000;
#define fro front
vi euler_list;
vi euler_depth;
vector<pair<ii, ll>> tintout(100005, pair<ii, ll>(ii(-1, -1), 0));
vector<vector<ii>> x(100005);
ll vis[100005];
ll hi[100005];
struct segtree{
ll dd, ht, mid;
ll val;
segtree *L, *R;
segtree(ll l,ll r){
dd = l, ht =r; mid = (dd+ht)/2;
if(l == r){
val = inf;
}else{
L = new segtree(dd, mid); R = new segtree(mid+1, ht);
val = min(L -> val, R -> val);
}
}
void update(ll pos, ll newval){
if(dd == ht){
val = newval;
}else{
if(pos <= mid){
L -> update(pos, newval);
}else{
R -> update(pos, newval);
}
val = min(L -> val, R -> val);
}
}
ll query(ll l, ll r){
if(l == dd && r == ht) return val;
if(r <= mid){
return L -> query(l, r);
}else if(l > mid){
return R -> query(l, r);
}
return min(L -> query(l, mid), R -> query(mid+1, r));
}
};
segtree tree(0, 2000005);
void euler(ll no,ll h){
if(vis[no] != -1){
return;
}
vis[no] = 1;
hi[no] = h;
euler_list.pb(no);
euler_depth.pb(h);
for(auto e:x[no]){
euler(e.fi, h + e.se);
euler_depth.pb(h);
euler_list.pb(no);
}
return ;
}
void Init(int N, int A[], int B[], int D[]) {
for(ll i = 0; i < N; ++i){
x[A[i]].pb(ii(B[i], D[i]));
x[B[i]].pb(ii(A[i], D[i]));
}
for(ll i = 0; i < 100005; ++i){
tintout[i].second = i;
}
memset(vis, -1, sizeof vis);
euler(0, 0);
for(ll i = 0; i < euler_list.size(); ++i){
if(tintout[euler_list[i]].fi.fi == -1)
tintout[euler_list[i]].fi.fi = i;
tintout[euler_list[i]].fi.se = i;
}
for(int i = 0; i < euler_depth.size(); ++i){
tree.update(i, euler_depth[i]);
}
}
long long Query(int S, int X[], int T, int Y[]) {
ll ans = inf;
for(ll i = 0; i < S; ++i){
for(ll j = 0; j < T; ++j){
int a = tintout[X[i]].fi.fi;
int b = tintout[Y[j]].fi.fi;
ll l = min(a, b);
a = tintout[X[i]].fi.se;
b = tintout[Y[j]].fi.se;
ll r = max(a, b);
ll LCA = tree.query(l, r);
if(LCA == tintout[X[i]].fi.fi || LCA == tintout[Y[i]].fi.fi){
ans = min(ans, abs(hi[X[i]] - hi[Y[j]])) ;
}
ans = min(ans, hi[X[i]] - LCA + hi[Y[j]] - LCA);
}
}
return ans;
}
Compilation message
factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:95:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
95 | for(ll i = 0; i < euler_list.size(); ++i){
| ~~^~~~~~~~~~~~~~~~~~~
factories.cpp:101:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
101 | for(int i = 0; i < euler_depth.size(); ++i){
| ~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
274 ms |
258152 KB |
Output is correct |
| 2 |
Execution timed out |
8042 ms |
275652 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
170 ms |
257872 KB |
Output is correct |
| 2 |
Runtime error |
2827 ms |
524292 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
274 ms |
258152 KB |
Output is correct |
| 2 |
Execution timed out |
8042 ms |
275652 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
