| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 89619 | liwi | Factories (JOI14_factories) | C++11 | 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>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<pair<int,int>, null_type, less<pair<int,int>>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
#define scan(x) do{while((x=getchar())<'0'); for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0');}while(0)
char _;
#define println printf("\n");
#define readln(x) getline(cin,x);
#define pb push_back
#define endl "\n"
#define MOD 1000000007
#define mp make_pair
#define MAXN 15
#define LOGN 25
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef unordered_map<int,int> umii;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<int,pii> triple;
typedef int8_t byte;
ll gcd(ll a, ll b) {return b == 0 ? a : gcd(b, a % b);}
ll fpow(ll b, ll exp, ll mod){if(exp == 0) return 1;ll t = fpow(b,exp/2,mod);if(exp&1) return t*t%mod*b%mod;return t*t%mod;}
ll divmod(ll i, ll j, ll mod){i%=mod,j%=mod;return i*fpow(j,mod-2,mod)%mod;}
int num_nodes,num_q,sz[MAXN],lvl[MAXN],par[MAXN],mxlvl,upd[MAXN],qcnt,A[MAXN],B[MAXN],D[MAXN];;
ll small[MAXN],dis[LOGN][MAXN];
bool done[MAXN];
vector<pii> tconnections[MAXN],connections[MAXN];
vector<int> nn[LOGN];
int getSz(int node, int prev){
sz[node] = 1;
for(pii check:tconnections[node]){
if(check.first == prev || done[check.first]) continue;
sz[node]+=getSz(check.first,node);
}
return sz[node];
}
int centroid(int node, int prev, int mx){
for(pii check:tconnections[node]){
if(check.first == prev || done[check.first]) continue;
if(sz[check.first]*2 > mx) return centroid(check.first,node,mx);
}
return node;
}
void getTree(int node, int prev, int mx, int lv, int dd){
mxlvl = max(mxlvl,lv);
getSz(node,-1);
node = centroid(node,-1,mx);
par[node] = prev;
lvl[node] = lv;
nn[lv].pb(node);
getSz(node,-1);
if(mx != num_nodes) connections[prev].pb(mp(node,dd));
done[node] = true;
for(pii check:tconnections[node]){
if(check.first == prev || done[check.first]) continue;
getTree(check.first,node,sz[check.first],lv+1,check.second);
}
}
void getDis(int node, int prev, int cur_l){
for(pii check:connections[node]){
if(check.first == prev) continue;
dis[cur_l][check.first] = dis[cur_l][node]+check.second;
getDis(check.first,node,cur_l);
}
}
void Init(int N, int A[MAXN], int B[MAXN], int D[MAXN]){
num_nodes = N;
for(int i=0; i<N-1; i++){
int a = A[i], b = B[i], dis = D[i];
tconnections[a].pb(mp(b,dis));
tconnections[b].pb(mp(a,dis));
}
getTree(0,0,num_nodes,0,0);
for(int i=0; i<=mxlvl; i++)
for(int check:nn[i])
getDis(check,par[check],i);
for(int i=0; i<num_nodes; i++)
small[i] = LONG_MAX;
}
ll Query(int s1, int X[MAXN], int s2, int Y[MAXN]){
++qcnt;
for(int i=0; i<s1; i++){
int current = X[i];
small[current] = 0, upd[current] = qcnt;
for(int k=0; k<lvl[X[i]]; k++){
ll nxt = dis[lvl[current]-1][X[i]];
if(upd[par[current]] != qcnt) small[par[current]] = nxt, upd[par[current]] = qcnt;
else small[par[current]] = min(small[par[current]],nxt);
current = par[current];
}
}
ll best = LONG_MAX;
for(int i=0; i<s2; i++){
int current = Y[i];
if(upd[current] == qcnt){
best = 0;
break;
}
for(int k=0; k<lvl[Y[i]]; k++){
if(upd[par[current]] == qcnt) best = min(best,dis[lvl[current]-1][Y[i]]+small[par[current]]);
current = par[current];
}
}
return best;
}
int main(){
// scanf(" %d %d",&num_nodes,&num_q);
// for(int i=0; i<num_nodes-1; i++)
// scanf(" %d %d %d",&A[i],&B[i],&D[i]);
// Init(num_nodes,A,B,D);
// for(int i=0; i<num_q; i++){
// int s1,s2; scanf(" %d %d",&s1,&s2);
// int first[MAXN],second[MAXN];
// for(int k=0; k<s1; k++)
// scanf(" %d",&first[k]);
// for(int k=0; k<s2; k++)
// scanf(" %d",&second[k]);
// printf("%lld\n",Query(s1,first,s2,second));
// }
}