#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
const int mxN = 600012;
typedef long long ll;
vector<pair<int, ll>> adj[mxN];
bool vis[mxN];
int sub[mxN];
//plasim se da ce biti sporo :/
int dfsSize(int s, int p = -1) {
sub[s] = 1;
for(auto b : adj[s]) {
int e = b.first;
if(e == p || vis[e])
continue;
dfsSize(e, s);
sub[s] += sub[e];
}
return sub[s];
}
int centroid(int s, int p, int n) {
for(auto b : adj[s]) {
int e = b.first;
if(e == p || vis[e])
continue;
if(sub[e] > n/2)
return centroid(e, s, n);
}
return s;
}
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);
}
};
unordered_map<int, ll, custom_hash> dist[mxN];
void dfs(int s, int p, int c) {
ll vrednost = -1;
for(auto b : adj[s]) {
int e = b.first;
if(e == p) {
vrednost = b.second;
break;
}
}
if(vrednost == -1) {
dist[c][s] = 0;
} else {
dist[c][s] = dist[c][p] + vrednost;
}
for(auto b : adj[s]) {
int e = b.first;
if(e == p || vis[e])
continue;
dfs(e, s, c);
}
}
int iznad[mxN];
void build(int s, int p = -1) {
int n = dfsSize(s);
int c = centroid(s, -1, n);
//int vel = 31 - __builtin_clz(n);
//dist[c].reserve(1<<vel);
//dist[c].max_load_factor(0.25);
dfs(c, -1, c);
iznad[c] = p;
vis[c] = true;
for(auto b : adj[c]) {
int e = b.first;
if(vis[e])
continue;
build(e, c);
}
}
ll mini[mxN];
void Init(int N, int A[], int B[], int D[]) {
for(int i = 0; i < N-1; ++i) {
int u = A[i], v = B[i];
ll w = D[i];
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
build(0);
for(int i = 0; i < N; ++i)
mini[i] = LLONG_MAX;
}
long long Query(int S, int X[], int T, int Y[]) {
//drzi za prve, za druge samo proveri
ll ans = LLONG_MAX;
for(int i = 0; i < S; ++i) {
int trenutni = X[i];
int iteriraj = trenutni;
while(iteriraj != -1) {
mini[iteriraj] = min(mini[iteriraj], dist[iteriraj][trenutni]);
iteriraj = iznad[iteriraj];
}
}
for(int i = 0; i < T; ++i) {
int trenutni = Y[i];
int iteriraj = trenutni;
while(iteriraj != -1) {
if(mini[iteriraj] != LLONG_MAX) {
ans = min(ans, mini[iteriraj] + dist[iteriraj][trenutni]);
}
iteriraj = iznad[iteriraj];
}
}
for(int i = 0; i < S; ++i) {
int iteriraj = X[i];
while(iteriraj != -1) {
mini[iteriraj] = LLONG_MAX;
iteriraj = iznad[iteriraj];
}
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
44 ms |
47792 KB |
Output is correct |
2 |
Correct |
959 ms |
58060 KB |
Output is correct |
3 |
Correct |
1212 ms |
59004 KB |
Output is correct |
4 |
Correct |
946 ms |
58836 KB |
Output is correct |
5 |
Correct |
1404 ms |
59920 KB |
Output is correct |
6 |
Correct |
441 ms |
56708 KB |
Output is correct |
7 |
Correct |
1168 ms |
59028 KB |
Output is correct |
8 |
Correct |
1191 ms |
59148 KB |
Output is correct |
9 |
Correct |
1407 ms |
59836 KB |
Output is correct |
10 |
Correct |
389 ms |
56840 KB |
Output is correct |
11 |
Correct |
1173 ms |
59072 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
47560 KB |
Output is correct |
2 |
Correct |
5411 ms |
438272 KB |
Output is correct |
3 |
Runtime error |
3839 ms |
524292 KB |
Execution killed with signal 9 |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
44 ms |
47792 KB |
Output is correct |
2 |
Correct |
959 ms |
58060 KB |
Output is correct |
3 |
Correct |
1212 ms |
59004 KB |
Output is correct |
4 |
Correct |
946 ms |
58836 KB |
Output is correct |
5 |
Correct |
1404 ms |
59920 KB |
Output is correct |
6 |
Correct |
441 ms |
56708 KB |
Output is correct |
7 |
Correct |
1168 ms |
59028 KB |
Output is correct |
8 |
Correct |
1191 ms |
59148 KB |
Output is correct |
9 |
Correct |
1407 ms |
59836 KB |
Output is correct |
10 |
Correct |
389 ms |
56840 KB |
Output is correct |
11 |
Correct |
1173 ms |
59072 KB |
Output is correct |
12 |
Correct |
32 ms |
47560 KB |
Output is correct |
13 |
Correct |
5411 ms |
438272 KB |
Output is correct |
14 |
Runtime error |
3839 ms |
524292 KB |
Execution killed with signal 9 |
15 |
Halted |
0 ms |
0 KB |
- |