oj.uz

Submission #724396

# Submission time Handle Problem Language Result Execution time Memory
724396 2023-04-15T07:39:52 Z rrrr10000 Factories (JOI14_factories) C++14
100 / 100
 7696 ms 245440 KB 
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n)  for(long long i=0;i<(long long)(n);i++)
#define REP(i,k,n) for(long long i=k;i<(long long)(n);i++)
#define pb emplace_back
#define lb(v,k) (lower_bound(all(v),(k))-v.begin())
#define ub(v,k) (upper_bound(all(v),(k))-v.begin())
#define fi first
#define se second
#define pi M_PI
#define PQ(T) priority_queue<T>
#define SPQ(T) priority_queue<T,vector<T>,greater<T>>
#define dame(a) {out(a);return 0;}
#define decimal cout<<fixed<<setprecision(15);
#define all(a) a.begin(),a.end()
#define rsort(a) {sort(all(a));reverse(all(a));}
#define dupli(a) {sort(all(a));a.erase(unique(all(a)),a.end());}
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef tuple<ll,ll,ll,ll> PPP;
using vi=vector<ll>;
using vvi=vector<vi>;
using vvvi=vector<vvi>;
using vvvvi=vector<vvvi>;
using vp=vector<P>;
using vvp=vector<vp>;
using vb=vector<bool>;
using vvb=vector<vb>;
const ll inf=1001001001001001001;
const ll INF=1001001001;
const ll mod=998244353;
const double eps=1e-10;
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outp(T a){cout<<'('<<a.fi<<','<<a.se<<')'<<'\n';}
template<class T> void outvp(T v){rep(i,v.size())cout<<'('<<v[i].fi<<','<<v[i].se<<')';cout<<'\n';}
template<class T> void outvvp(T v){rep(i,v.size())outvp(v[i]);}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
template<class T> void outvv(T v){rep(i,v.size())outv(v[i]);}
template<class T> bool isin(T x,T l,T r){return (l)<=(x)&&(x)<=(r);}
template<class T> void yesno(T b){if(b)out("yes");else out("no");}
template<class T> void YesNo(T b){if(b)out("Yes");else out("No");}
template<class T> void YESNO(T b){if(b)out("YES");else out("NO");}
template<class T> void outset(T s){auto itr=s.begin();while(itr!=s.end()){if(itr!=s.begin())cout<<' ';cout<<*itr;itr++;}cout<<'\n';}
void outs(ll a,ll b){if(a>=inf-100)out(b);else out(a);}
ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);}
ll modpow(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
#include "factories.h"
vvi table;
vi in,dep,dep2;
vi dis;
vvp G,g;
void Init(int n,int a[],int b[],int d[]){
    g=vvp(n);
    rep(i,n-1){
        g[a[i]].pb(b[i],d[i]);
        g[b[i]].pb(a[i],d[i]);
    }
    table=vvi(n,vi(20));dep=vi(n);dep2=vi(n);
    in=vi(n);
    ll c=0;
    function<void(ll,ll)> dfs=[&](ll i,ll p){
        in[i]=c++;
        table[i][0]=p;
        for(auto x:g[i])if(x.fi!=p){
            dep[x.fi]=dep[i]+1;dep2[x.fi]=dep2[i]+x.se;
            dfs(x.fi,i);
        }
    };dfs(0,-1);
    rep(k,19)rep(i,n)if(table[i][k]!=-1)table[i][k+1]=table[table[i][k]][k];
    G=vvp(n);dis=vi(n,inf);
}
bool comp(ll a,ll b){
    return in[a]<in[b];
}
ll lca(ll a,ll b){
    if(dep[a]>dep[b])swap(a,b);
    ll dif=dep[b]-dep[a];
    rep(i,20)if(dif>>i&1)b=table[b][i];
    if(a==b)return a;
    for(int i=19;i>=0;i--)if(table[a][i]!=table[b][i]){
        a=table[a][i];b=table[b][i];
    }
    return table[a][0];
}
ll Query(int s,int a[],int t,int b[]){
    vi al;
    rep(i,s)al.pb(a[i]);
    rep(i,t)al.pb(b[i]);
    sort(all(al),comp);
    rep(i,s+t-1)al.pb(lca(al[i],al[i+1]));
    sort(all(al),comp);
    al.erase(unique(all(al)),al.end());
    rep(i,al.size()-1){
        ll l=lca(al[i],al[i+1]),t=dep2[al[i+1]]-dep2[l];
        G[l].pb(al[i+1],t);
        G[al[i+1]].pb(l,t);
    }
    rep(i,s){
        dis[a[i]]=0;
    }
    auto dfs=[&](auto && self,ll i,ll p) -> void {
        for(auto x:G[i])if(x.fi!=p){
            self(self,x.fi,i);
            chmin(dis[i],dis[x.fi]+x.se);
        }
    };dfs(dfs,al[0],-1);
    auto dfs2=[&](auto && self,ll i,ll p) -> void {
        for(auto x:G[i])if(x.fi!=p){
            chmin(dis[x.fi],dis[i]+x.se);
            self(self,x.fi,i);
        }
    };dfs2(dfs2,al[0],-1);
    ll ans=inf;
    rep(i,t)chmin(ans,dis[b[i]]);
    for(ll x:al){
        G[x]=vp(0);
        dis[x]=inf;
    }
    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 960 KB Output is correct
2 Correct 1362 ms 19632 KB Output is correct
3 Correct 1561 ms 19596 KB Output is correct
4 Correct 1414 ms 20072 KB Output is correct
5 Correct 1164 ms 20040 KB Output is correct
6 Correct 878 ms 19600 KB Output is correct
7 Correct 1549 ms 19660 KB Output is correct
8 Correct 1408 ms 19804 KB Output is correct
9 Correct 1126 ms 20168 KB Output is correct
10 Correct 862 ms 19652 KB Output is correct
11 Correct 1584 ms 19464 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 596 KB Output is correct
2 Correct 2381 ms 194384 KB Output is correct
3 Correct 4151 ms 199620 KB Output is correct
4 Correct 1545 ms 191772 KB Output is correct
5 Correct 2871 ms 242340 KB Output is correct
6 Correct 4461 ms 201116 KB Output is correct
7 Correct 3959 ms 58492 KB Output is correct
8 Correct 1504 ms 57764 KB Output is correct
9 Correct 2650 ms 64556 KB Output is correct
10 Correct 3811 ms 59848 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 960 KB Output is correct
2 Correct 1362 ms 19632 KB Output is correct
3 Correct 1561 ms 19596 KB Output is correct
4 Correct 1414 ms 20072 KB Output is correct
5 Correct 1164 ms 20040 KB Output is correct
6 Correct 878 ms 19600 KB Output is correct
7 Correct 1549 ms 19660 KB Output is correct
8 Correct 1408 ms 19804 KB Output is correct
9 Correct 1126 ms 20168 KB Output is correct
10 Correct 862 ms 19652 KB Output is correct
11 Correct 1584 ms 19464 KB Output is correct
12 Correct 4 ms 596 KB Output is correct
13 Correct 2381 ms 194384 KB Output is correct
14 Correct 4151 ms 199620 KB Output is correct
15 Correct 1545 ms 191772 KB Output is correct
16 Correct 2871 ms 242340 KB Output is correct
17 Correct 4461 ms 201116 KB Output is correct
18 Correct 3959 ms 58492 KB Output is correct
19 Correct 1504 ms 57764 KB Output is correct
20 Correct 2650 ms 64556 KB Output is correct
21 Correct 3811 ms 59848 KB Output is correct
22 Correct 5351 ms 209504 KB Output is correct
23 Correct 4827 ms 212692 KB Output is correct
24 Correct 6446 ms 213824 KB Output is correct
25 Correct 6627 ms 216628 KB Output is correct
26 Correct 7696 ms 207632 KB Output is correct
27 Correct 5022 ms 245440 KB Output is correct
28 Correct 3117 ms 208688 KB Output is correct
29 Correct 7244 ms 206884 KB Output is correct
30 Correct 7340 ms 205844 KB Output is correct
31 Correct 7358 ms 207160 KB Output is correct
32 Correct 2810 ms 71540 KB Output is correct
33 Correct 2130 ms 62812 KB Output is correct
34 Correct 3570 ms 55868 KB Output is correct
35 Correct 3242 ms 55780 KB Output is correct
36 Correct 4375 ms 57048 KB Output is correct
37 Correct 4207 ms 56892 KB Output is correct