oj.uz

Submission #377748

# Submission time Handle Problem Language Result Execution time Memory
377748 2021-03-14T23:06:59 Z rrrr10000 Factories (JOI14_factories) C++14
33 / 100
 8000 ms 223792 KB 
#include <bits/stdc++.h>
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
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;
vb memo;
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);
    memo=vb(n,false);
}
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);
    }
    SPQ(P) pq;
    rep(i,s){
        dis[a[i]]=0;
        pq.push(P(0,a[i]));
    }
    rep(i,t)memo[b[i]]=true;
    ll ans;
    while(!pq.empty()){
        auto t=pq.top();pq.pop();
        if(t.fi!=dis[t.se])continue;
        if(memo[t.se]){
            ans=t.fi;break;
        }
        for(auto x:G[t.se])if(chmin(dis[x.fi],t.fi+x.se))pq.push(P(dis[x.fi],x.fi));
    }
    for(ll x:al){
        G[x]=vp(0);
        dis[x]=inf;
    }
    rep(i,t)memo[b[i]]=false;
    return ans;
}

Compilation message

factories.cpp: In function 'll Query(int, int*, int, int*)':
factories.cpp:126:12: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
  126 |     return ans;
      |            ^~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 748 KB Output is correct
2 Correct 1705 ms 10864 KB Output is correct
3 Correct 1821 ms 10380 KB Output is correct
4 Correct 1746 ms 10764 KB Output is correct
5 Correct 1453 ms 10940 KB Output is correct
6 Correct 1205 ms 10408 KB Output is correct
7 Correct 1837 ms 10268 KB Output is correct
8 Correct 1793 ms 10640 KB Output is correct
9 Correct 1496 ms 10824 KB Output is correct
10 Correct 1195 ms 10268 KB Output is correct
11 Correct 1781 ms 10220 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 620 KB Output is correct
2 Correct 3096 ms 175832 KB Output is correct
3 Correct 5356 ms 181624 KB Output is correct
4 Correct 1992 ms 173640 KB Output is correct
5 Correct 3725 ms 223792 KB Output is correct
6 Correct 5716 ms 182792 KB Output is correct
7 Correct 5798 ms 44780 KB Output is correct
8 Correct 2078 ms 44276 KB Output is correct
9 Correct 3809 ms 50656 KB Output is correct
10 Correct 5806 ms 45940 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 748 KB Output is correct
2 Correct 1705 ms 10864 KB Output is correct
3 Correct 1821 ms 10380 KB Output is correct
4 Correct 1746 ms 10764 KB Output is correct
5 Correct 1453 ms 10940 KB Output is correct
6 Correct 1205 ms 10408 KB Output is correct
7 Correct 1837 ms 10268 KB Output is correct
8 Correct 1793 ms 10640 KB Output is correct
9 Correct 1496 ms 10824 KB Output is correct
10 Correct 1195 ms 10268 KB Output is correct
11 Correct 1781 ms 10220 KB Output is correct
12 Correct 6 ms 620 KB Output is correct
13 Correct 3096 ms 175832 KB Output is correct
14 Correct 5356 ms 181624 KB Output is correct
15 Correct 1992 ms 173640 KB Output is correct
16 Correct 3725 ms 223792 KB Output is correct
17 Correct 5716 ms 182792 KB Output is correct
18 Correct 5798 ms 44780 KB Output is correct
19 Correct 2078 ms 44276 KB Output is correct
20 Correct 3809 ms 50656 KB Output is correct
21 Correct 5806 ms 45940 KB Output is correct
22 Correct 6790 ms 186772 KB Output is correct
23 Correct 6216 ms 191584 KB Output is correct
24 Correct 7445 ms 192032 KB Output is correct
25 Correct 7692 ms 194096 KB Output is correct
26 Execution timed out 8068 ms 183968 KB Time limit exceeded
27 Halted 0 ms 0 KB -