oj.uz

Submission #990706

# Submission time Handle Problem Language Result Execution time Memory
990706 2024-05-31T04:56:08 Z vjudge1 Factories (JOI14_factories) C++17
100 / 100
 4556 ms 178440 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 33 ms 52056 KB Output is correct
2 Correct 1318 ms 67900 KB Output is correct
3 Correct 1498 ms 67840 KB Output is correct
4 Correct 1334 ms 67924 KB Output is correct
5 Correct 1375 ms 68224 KB Output is correct
6 Correct 1224 ms 67920 KB Output is correct
7 Correct 1488 ms 67920 KB Output is correct
8 Correct 1439 ms 67976 KB Output is correct
9 Correct 1363 ms 68216 KB Output is correct
10 Correct 1240 ms 67924 KB Output is correct
11 Correct 1437 ms 67844 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 51804 KB Output is correct
2 Correct 1869 ms 150188 KB Output is correct
3 Correct 2293 ms 153428 KB Output is correct
4 Correct 1358 ms 147364 KB Output is correct
5 Correct 2701 ms 177748 KB Output is correct
6 Correct 2418 ms 154332 KB Output is correct
7 Correct 2646 ms 91048 KB Output is correct
8 Correct 1560 ms 90532 KB Output is correct
9 Correct 2266 ms 94292 KB Output is correct
10 Correct 2628 ms 91752 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 52056 KB Output is correct
2 Correct 1318 ms 67900 KB Output is correct
3 Correct 1498 ms 67840 KB Output is correct
4 Correct 1334 ms 67924 KB Output is correct
5 Correct 1375 ms 68224 KB Output is correct
6 Correct 1224 ms 67920 KB Output is correct
7 Correct 1488 ms 67920 KB Output is correct
8 Correct 1439 ms 67976 KB Output is correct
9 Correct 1363 ms 68216 KB Output is correct
10 Correct 1240 ms 67924 KB Output is correct
11 Correct 1437 ms 67844 KB Output is correct
12 Correct 11 ms 51804 KB Output is correct
13 Correct 1869 ms 150188 KB Output is correct
14 Correct 2293 ms 153428 KB Output is correct
15 Correct 1358 ms 147364 KB Output is correct
16 Correct 2701 ms 177748 KB Output is correct
17 Correct 2418 ms 154332 KB Output is correct
18 Correct 2646 ms 91048 KB Output is correct
19 Correct 1560 ms 90532 KB Output is correct
20 Correct 2266 ms 94292 KB Output is correct
21 Correct 2628 ms 91752 KB Output is correct
22 Correct 3078 ms 155568 KB Output is correct
23 Correct 3088 ms 156416 KB Output is correct
24 Correct 3521 ms 159148 KB Output is correct
25 Correct 3614 ms 160620 KB Output is correct
26 Correct 4536 ms 158712 KB Output is correct
27 Correct 3748 ms 178440 KB Output is correct
28 Correct 2298 ms 154624 KB Output is correct
29 Correct 4479 ms 158544 KB Output is correct
30 Correct 4397 ms 157808 KB Output is correct
31 Correct 4556 ms 158548 KB Output is correct
32 Correct 1875 ms 95308 KB Output is correct
33 Correct 1555 ms 91072 KB Output is correct
34 Correct 1877 ms 89500 KB Output is correct
35 Correct 1922 ms 89496 KB Output is correct
36 Correct 2282 ms 90192 KB Output is correct
37 Correct 2322 ms 90452 KB Output is correct