oj.uz

Submission #990742

# Submission time Handle Problem Language Result Execution time Memory
990742 2024-05-31T07:06:47 Z boyliguanhan Factories (JOI14_factories) C++17
100 / 100
 4322 ms 159068 KB 
#include "factories.h"
#define M 1<<19
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll TRE[2][2*M],dep[M],dd[M];
ll q(ll*T,int i,int l,int r,int tl,int tr){
    if(l>tr||tl>r) return 1e18;
    if(tl<=l&&r<=tr) return T[i];
    return min(q(T,i*2,l,l+r>>1,tl,tr),
            q(T,i*2+1,l+r+2>>1,r,tl,tr));
}
void upd(ll*T,int i,int l,int r,int p,ll x){
    if(l==r)return void(T[i]=x);
    if(l+r>>1<p)
        upd(T,i*2+1,l+r+2>>1,r,p,x);
    else upd(T,i*2,l,l+r>>1,p,x);
    T[i]=min(T[i*2],T[i*2+1]);
}
int pos[M],in[M],out[M],bj[M][20],CC,n;
vector<pair<int,ll>>adj[M];
void dfs(int n){
    for(int i=1;i<20;i++)
        bj[n][i]=bj[bj[n][i-1]][i-1];
    in[n]=++CC,dd[n]=dd[bj[n][0]]+1;
    for(auto[i,w]:adj[n]) if(i-bj[n][0])
        dep[i]=dep[n]+w,bj[i][0]=n,dfs(i);
    out[n]=CC;
}
void Init(int N, int A[], int B[], int D[]) {
    for(int i=1;i<2*M;i++)
        TRE[1][i]=TRE[0][i]=1e18;
    for(int i=0;i<N-1;i++)
        adj[A[i]].push_back({B[i],D[i]}),
        adj[B[i]].push_back({A[i],D[i]});
    n=N,dfs(0);
}
int lca(int a,int b){
    if(dd[a]>dd[b])swap(a,b);
    for(int i=20;i--;)
        if(dd[bj[b][i]]>=dd[a])
            b=bj[b][i];
    if(a==b)return a;
    for(int i=20;i--;)
        if(bj[b][i]-bj[a][i])
            a=bj[a][i],b=bj[b][i];
    return bj[a][0];
}
long long Query(int S, int X[], int T, int Y[]) {
    ll ans=1e18;
    vector<int>v;
    for(int i=0;i<S;i++) v.push_back(X[i]),
        upd(*TRE,1,1,n,in[X[i]],dep[X[i]]);
    for(int i=0;i<T;i++) v.push_back(Y[i]),
        upd(TRE[1],1,1,n,in[Y[i]],dep[Y[i]]);
    sort(v.begin(),v.end(),[](int a,int b){return in[a]<in[b];});
    for(int i=1;i<S+T;i++){
        int x=lca(v[i],v[i-1]);
        ans=min(ans,q(*TRE,1,1,n,in[x],out[x])
        +q(TRE[1],1,1,n,in[x],out[x])-2*dep[x]);
    }
    for(auto i:v)upd(*TRE,1,1,n,in[i],1e18);
    for(auto i:v)upd(TRE[1],1,1,n,in[i],1e18);
    return ans;
}

Compilation message

factories.cpp: In function 'long long int q(long long int*, int, int, int, int, int)':
factories.cpp:10:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   10 |     return min(q(T,i*2,l,l+r>>1,tl,tr),
      |                          ~^~
factories.cpp:11:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   11 |             q(T,i*2+1,l+r+2>>1,r,tl,tr));
      |                       ~~~^~
factories.cpp: In function 'void upd(long long int*, int, int, int, int, long long int)':
factories.cpp:15:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   15 |     if(l+r>>1<p)
      |        ~^~
factories.cpp:16:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   16 |         upd(T,i*2+1,l+r+2>>1,r,p,x);
      |                     ~~~^~
factories.cpp:17:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   17 |     else upd(T,i*2,l,l+r>>1,p,x);
      |                      ~^~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 51940 KB Output is correct
2 Correct 1347 ms 58432 KB Output is correct
3 Correct 1499 ms 58452 KB Output is correct
4 Correct 1420 ms 58512 KB Output is correct
5 Correct 1402 ms 58708 KB Output is correct
6 Correct 1233 ms 58448 KB Output is correct
7 Correct 1490 ms 58448 KB Output is correct
8 Correct 1429 ms 58504 KB Output is correct
9 Correct 1405 ms 58752 KB Output is correct
10 Correct 1185 ms 58452 KB Output is correct
11 Correct 1477 ms 58240 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 51804 KB Output is correct
2 Correct 1748 ms 131252 KB Output is correct
3 Correct 2771 ms 135560 KB Output is correct
4 Correct 1632 ms 129060 KB Output is correct
5 Correct 3259 ms 159068 KB Output is correct
6 Correct 3875 ms 135644 KB Output is correct
7 Correct 2613 ms 77292 KB Output is correct
8 Correct 1473 ms 76324 KB Output is correct
9 Correct 2155 ms 80284 KB Output is correct
10 Correct 2458 ms 77704 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 51940 KB Output is correct
2 Correct 1347 ms 58432 KB Output is correct
3 Correct 1499 ms 58452 KB Output is correct
4 Correct 1420 ms 58512 KB Output is correct
5 Correct 1402 ms 58708 KB Output is correct
6 Correct 1233 ms 58448 KB Output is correct
7 Correct 1490 ms 58448 KB Output is correct
8 Correct 1429 ms 58504 KB Output is correct
9 Correct 1405 ms 58752 KB Output is correct
10 Correct 1185 ms 58452 KB Output is correct
11 Correct 1477 ms 58240 KB Output is correct
12 Correct 10 ms 51804 KB Output is correct
13 Correct 1748 ms 131252 KB Output is correct
14 Correct 2771 ms 135560 KB Output is correct
15 Correct 1632 ms 129060 KB Output is correct
16 Correct 3259 ms 159068 KB Output is correct
17 Correct 3875 ms 135644 KB Output is correct
18 Correct 2613 ms 77292 KB Output is correct
19 Correct 1473 ms 76324 KB Output is correct
20 Correct 2155 ms 80284 KB Output is correct
21 Correct 2458 ms 77704 KB Output is correct
22 Correct 2786 ms 131272 KB Output is correct
23 Correct 3012 ms 131968 KB Output is correct
24 Correct 3296 ms 134872 KB Output is correct
25 Correct 3341 ms 136076 KB Output is correct
26 Correct 4208 ms 134480 KB Output is correct
27 Correct 3493 ms 153844 KB Output is correct
28 Correct 2160 ms 129968 KB Output is correct
29 Correct 4283 ms 134148 KB Output is correct
30 Correct 4159 ms 133628 KB Output is correct
31 Correct 4322 ms 134088 KB Output is correct
32 Correct 1924 ms 81736 KB Output is correct
33 Correct 1562 ms 77092 KB Output is correct
34 Correct 1935 ms 75940 KB Output is correct
35 Correct 1942 ms 75936 KB Output is correct
36 Correct 2376 ms 76688 KB Output is correct
37 Correct 2456 ms 76632 KB Output is correct