| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 645803 | tamthegod | Factories (JOI14_factories) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 1e6 + 5;
const int mod = 1e9 + 7;
const ll oo = 1e9;
vector<pair<int, int>> adj[maxN];
int n, q;
vector<int> tour;
int pos[maxN];
int rmq[maxN][21];
int lg[maxN];
int depth[maxN];
vector<int> vc[maxN];
int f[maxN];
int F[maxN];
int dp[maxN];
int vis[maxN];
int parCent[maxN];
void Log()
{
for(int i=2; i<maxN; i++)
lg[i] = lg[i / 2] + 1;
}
void predfs(int u, int par)
{
pos[u] = tour.size();
tour.pb(u);
for(auto a : adj[u])
{
int v = a.fi, w = a.se;
if(v == par) continue;
depth[v] = depth[u] + 1;
f[v] = f[u] + w;
predfs(v, u);
tour.pb(u);
}
}
int mini(int u, int v)
{
return depth[u] < depth[v] ? u : v;
}
int LCA(int u, int v)
{
int l = min(pos[u], pos[v]), r = max(pos[u], pos[v]);
int k = lg[r - l + 1];
return mini(rmq[l][k], rmq[r - (1 << k) + 1][k]);
}
int dist(int u, int v)
{
return f[u] + f[v] - 2 * f[LCA(u, v)];
}
int dfs(int u, int par)
{
dp[u] = 1;
for(auto a : adj[u])
{
int v = a.fi;
if(v == par || vis[v])
continue;
dp[u] += dfs(v, u);
}
return dp[u];
}
int Find_Centroid(int u, int par, int sz)
{
for(auto a : adj[u])
{
int v = a.fi;
if(v == par || vis[v])
continue;
if(dp[v] > sz / 2)
return Find_Centroid(v, u, sz);
}
return u;
}
int Decompose(int u)
{
int root = Find_Centroid(u, 0, dfs(u, 0));
vis[root] = 1;
for(auto a : adj[root])
{
int v = a.fi;
if(vis[v])
continue;
parCent[Decompose(v)] = root;
}
return root;
}
void update(int u)
{
for(int v=u; v; v=parCent[v])
{
F[v] = min(F[v], f[u] - 2 * f[v]);
}
}
void del(int u)
{
for(int v=u; v; v=parCent[v])
{
F[v] = oo;
}
}
int get(int u)
{
int res = oo;
for(int v=u; v; v=parCent[v]) res = min(res, F[v] + f[u]);
return res;
}
void Init(int N, int A[], int B[], int D[])
{
n = N;
for(int i=0; i<n; i++)
{
int u = A[i] + 1, v = B[i] + 1, w = D[i];
adj[u].pb({v, w});
adj[v].pb({u, w});
}
Log();
depth[1] = 1;
tour.clear();
//cout << Decompose(1);return;
predfs(Decompose(1), 0);
for (int i = 0; i < tour.size(); i++)
{
rmq[i][0] = tour[i];
}
for (int i = 1; i <=20; i++)
{
for (int j = 0; j < tour.size(); j++)
{
if (j + (1 << (i - 1)) >= tour.size())
rmq[j][i] = rmq[j][i - 1];
else
rmq[j][i] = mini(rmq[j][i - 1], rmq[j + (1 << (i - 1))][i - 1]);
}
}
// cout << LCA(4, 7);return;
fill(F, F + n + 1, oo);
//cout << dist(4, 7);return;
}
long long Query(int S, int X[], int T, int Y[])
{
for(int i=0; i<S; i++)
{
int u = X[i] + 1;
update(u);
}
int res = oo;
for(int i=0; i<T; i++)
{
int u = Y[i] + 1;
res = min(res, get(u));
}
return res;
}
void ReadInput()
{
cin >> n >> q;
for(int i=1; i<n; i++)
{
int u, v, w;
cin >> u >> v >> w;
u++;
v++;
adj[u].pb({v, w});
adj[v].pb({u, w});
}
}
void Solve()
{
Log();
depth[1] = 1;
tour.clear();
//cout << Decompose(1);return;
predfs(Decompose(1), 0);
for (int i = 0; i < tour.size(); i++)
{
rmq[i][0] = tour[i];
}
for (int i = 1; i <=20; i++)
{
for (int j = 0; j < tour.size(); j++)
{
if (j + (1 << (i - 1)) >= tour.size())
rmq[j][i] = rmq[j][i - 1];
else
rmq[j][i] = mini(rmq[j][i - 1], rmq[j + (1 << (i - 1))][i - 1]);
}
}
// cout << LCA(4, 7);return;
fill(F, F + n + 1, oo);
//cout << dist(4, 7);return;
while(q--)
{
int x, y;
cin >> x >> y;
vector<int> vc;
for(int i=1; i<=x; i++)
{
int u;
cin >> u;
u++;
update(u);
vc.pb(u);
}
int res = oo;
for(int i=1; i<=y; i++)
{
int v;
cin >> v;
v++;
res = min(res, get(v));
}
for(int u : vc) del(u);
cout << res << '\n';
}
}
/*int32_t main()
{
freopen("x.inp", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ReadInput();
Solve();
}*/
#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 1e6 + 5;
const int mod = 1e9 + 7;
const ll oo = 1e9;
vector<pair<int, int>> adj[maxN];
int n, q;
vector<int> tour;
int pos[maxN];
int rmq[maxN][21];
int lg[maxN];
int depth[maxN];
vector<int> vc[maxN];
int f[maxN];
int F[maxN];
int dp[maxN];
int vis[maxN];
int parCent[maxN];
void Log()
{
for(int i=2; i<maxN; i++)
lg[i] = lg[i / 2] + 1;
}
void predfs(int u, int par)
{
pos[u] = tour.size();
tour.pb(u);
for(auto a : adj[u])
{
int v = a.fi, w = a.se;
if(v == par) continue;
depth[v] = depth[u] + 1;
f[v] = f[u] + w;
predfs(v, u);
tour.pb(u);
}
}
int mini(int u, int v)
{
return depth[u] < depth[v] ? u : v;
}
int LCA(int u, int v)
{
int l = min(pos[u], pos[v]), r = max(pos[u], pos[v]);
int k = lg[r - l + 1];
return mini(rmq[l][k], rmq[r - (1 << k) + 1][k]);
}
int dist(int u, int v)
{
return f[u] + f[v] - 2 * f[LCA(u, v)];
}
int dfs(int u, int par)
{
dp[u] = 1;
for(auto a : adj[u])
{
int v = a.fi;
if(v == par || vis[v])
continue;
dp[u] += dfs(v, u);
}
return dp[u];
}
int Find_Centroid(int u, int par, int sz)
{
for(auto a : adj[u])
{
int v = a.fi;
if(v == par || vis[v])
continue;
if(dp[v] > sz / 2)
return Find_Centroid(v, u, sz);
}
return u;
}
int Decompose(int u)
{
int root = Find_Centroid(u, 0, dfs(u, 0));
vis[root] = 1;
for(auto a : adj[root])
{
int v = a.fi;
if(vis[v])
continue;
parCent[Decompose(v)] = root;
}
return root;
}
void update(int u)
{
for(int v=u; v; v=parCent[v])
{
F[v] = min(F[v], f[u] - 2 * f[v]);
}
}
void del(int u)
{
for(int v=u; v; v=parCent[v])
{
F[v] = oo;
}
}
int get(int u)
{
int res = oo;
for(int v=u; v; v=parCent[v]) res = min(res, F[v] + f[u]);
return res;
}
void Init(int N, int A[], int B[], int D[])
{
n = N;
for(int i=0; i<n; i++)
{
int u = A[i] + 1, v = B[i] + 1, w = D[i];
adj[u].pb({v, w});
adj[v].pb({u, w});
}
Log();
depth[1] = 1;
tour.clear();
//cout << Decompose(1);return;
predfs(Decompose(1), 0);
for (int i = 0; i < tour.size(); i++)
{
rmq[i][0] = tour[i];
}
for (int i = 1; i <=20; i++)
{
for (int j = 0; j < tour.size(); j++)
{
if (j + (1 << (i - 1)) >= tour.size())
rmq[j][i] = rmq[j][i - 1];
else
rmq[j][i] = mini(rmq[j][i - 1], rmq[j + (1 << (i - 1))][i - 1]);
}
}
// cout << LCA(4, 7);return;
fill(F, F + n + 1, oo);
//cout << dist(4, 7);return;
}
long long Query(int S, int X[], int T, int Y[])
{
for(int i=0; i<S; i++)
{
int u = X[i] + 1;
update(u);
}
int res = oo;
for(int i=0; i<T; i++)
{
int u = Y[i] + 1;
res = min(res, get(u));
}
return res;
}
void ReadInput()
{
cin >> n >> q;
for(int i=1; i<n; i++)
{
int u, v, w;
cin >> u >> v >> w;
u++;
v++;
adj[u].pb({v, w});
adj[v].pb({u, w});
}
}
void Solve()
{
Log();
depth[1] = 1;
tour.clear();
//cout << Decompose(1);return;
predfs(Decompose(1), 0);
for (int i = 0; i < tour.size(); i++)
{
rmq[i][0] = tour[i];
}
for (int i = 1; i <=20; i++)
{
for (int j = 0; j < tour.size(); j++)
{
if (j + (1 << (i - 1)) >= tour.size())
rmq[j][i] = rmq[j][i - 1];
else
rmq[j][i] = mini(rmq[j][i - 1], rmq[j + (1 << (i - 1))][i - 1]);
}
}
// cout << LCA(4, 7);return;
fill(F, F + n + 1, oo);
//cout << dist(4, 7);return;
while(q--)
{
int x, y;
cin >> x >> y;
vector<int> vc;
for(int i=1; i<=x; i++)
{
int u;
cin >> u;
u++;
update(u);
vc.pb(u);
}
int res = oo;
for(int i=1; i<=y; i++)
{
int v;
cin >> v;
v++;
res = min(res, get(v));
}
for(int u : vc) del(u);
cout << res << '\n';
}
}
/*int32_t main()
{
freopen("x.inp", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ReadInput();
Solve();
}*/