oj.uz

Submission #899087

# Submission time Handle Problem Language Result Execution time Memory
899087 2024-01-05T13:11:56 Z Denkata Factories (JOI14_factories) C++14
100 / 100
 4550 ms 240212 KB 
#include<bits/stdc++.h>
#include "factories.h"
//#include "grader.cpp"
using namespace std;
const int maxn = 5e5+3;
int i,j,p,q,n,m,k,par[maxn],sz[maxn],tin[maxn],tout[maxn],br,l,timer,lasttime[maxn],cnt;
long long ans[maxn],raz[maxn];
vector <int> up[maxn];
///moje i set
struct Put
{
    int v;
    long long d;
};
bool operator<(Put a,Put b)
{
    return a.v<b.v;
}
set <Put> v[maxn];
void dfs(int u,int p)
{
    tin[u]=++timer;
    up[u][0]=p;
    for(int j=1;j<=l;j++)
    {
        up[u][j]=up[up[u][j-1]][j-1];
    }
    for(auto i:v[u])
    {
        int q=i.v;
        if(q!=p)
        {
            raz[q]=raz[u]+i.d;
            dfs(q,u);
        }
    }
    //cout<<u<<" "<<p<<endl;
    tout[u]=++timer;
}
bool upper(int a,int b)
{
    return (tin[a]<=tin[b] && tout[a]>=tout[b]);
}
int lca(int a,int b)
{
    if(upper(a,b))return a;
    if(upper(b,a))return b;
    for(int ii=l;ii>=0;ii--)
    {
        if(!upper(up[a][ii],b))
            a=up[a][ii];
    }
    return up[a][0];
}
int find_size(int u,int p)
{
    sz[u] = 1;
    for(auto i:v[u])
        if(i.v!=p)sz[u]+=find_size(i.v,u);
    return sz[u];
}
int find_centroid(int u,int p,int N)
{
    for(auto i:v[u])
        if(i.v!=p && sz[i.v]>N/2)return find_centroid(i.v,u,N);
    return u;
}
void centroid_decomposition(int u,int p)
{
    //cout<<u<<" centr "<<p<<endl;
    int N = find_size(u,p);
    int c = find_centroid(u,p,N);
    par[c] = p;
    //cout<<"par of "<<c<<" is "<<p<<endl;
    stack <pair <int,int>> st;
    for(auto i:v[c])
    {
        v[i.v].erase({c,i.d});
        centroid_decomposition(i.v,c);
    }
    v[c].clear();

}
void Init(int N, int A[], int B[], int D[])
{
    n = N;
    for(i=0;i<=N-2;i++)
    {
        p = A[i];q = B[i];k = D[i];
        p++;q++;
       // cout<<p<<" "<<q<<" "<<k<<endl;
        v[p].insert({q,k});
        v[q].insert({p,k});
    }
    while((1<<l)<=n)
        l++;
    for(i=0;i<=n+1;i++)
        up[i].resize(l+6);
    tout[0] = INT_MAX;
    dfs(1,0);
    //
    centroid_decomposition(1,0);
    //cout<<"krai"<<endl;
    for(i=1;i<=n;i++)
        ans[i] = LLONG_MAX;
}
long long dist(int u,int u2)
{
    return raz[u]+raz[u2]-2*raz[lca(u,u2)];
}
void add(int ver)
{
    for(j=ver;j!=0;j=par[j])
    {
        if(lasttime[j]!=cnt)
            ans[j] = dist(ver,j),lasttime[j] = cnt;
        else ans[j] = min(ans[j],dist(ver,j));
    }
}
long long Query(int S, int X[], int T, int Y[])
{
    ///+1 to all vertices
    long long otg = LLONG_MAX;
    ++cnt;
    for(i=0;i<S;i++)
    {
        add(X[i]+1);
    }
    for(i=0;i<T;i++)
    {
        p = Y[i]+1;
        for(j=p;j!=0;j=par[j])
            if(lasttime[j]==cnt)otg = min(otg,dist(p,j)+ans[j]);
    }


    return otg;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 68444 KB Output is correct
2 Correct 330 ms 83024 KB Output is correct
3 Correct 554 ms 82992 KB Output is correct
4 Correct 476 ms 83240 KB Output is correct
5 Correct 427 ms 83280 KB Output is correct
6 Correct 177 ms 82900 KB Output is correct
7 Correct 529 ms 83028 KB Output is correct
8 Correct 513 ms 82956 KB Output is correct
9 Correct 435 ms 83256 KB Output is correct
10 Correct 173 ms 82772 KB Output is correct
11 Correct 531 ms 82864 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 66392 KB Output is correct
2 Correct 1920 ms 212480 KB Output is correct
3 Correct 2651 ms 215016 KB Output is correct
4 Correct 1203 ms 212052 KB Output is correct
5 Correct 2987 ms 239852 KB Output is correct
6 Correct 2843 ms 216076 KB Output is correct
7 Correct 1217 ms 111704 KB Output is correct
8 Correct 340 ms 111132 KB Output is correct
9 Correct 1107 ms 114980 KB Output is correct
10 Correct 1271 ms 112176 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 68444 KB Output is correct
2 Correct 330 ms 83024 KB Output is correct
3 Correct 554 ms 82992 KB Output is correct
4 Correct 476 ms 83240 KB Output is correct
5 Correct 427 ms 83280 KB Output is correct
6 Correct 177 ms 82900 KB Output is correct
7 Correct 529 ms 83028 KB Output is correct
8 Correct 513 ms 82956 KB Output is correct
9 Correct 435 ms 83256 KB Output is correct
10 Correct 173 ms 82772 KB Output is correct
11 Correct 531 ms 82864 KB Output is correct
12 Correct 12 ms 66392 KB Output is correct
13 Correct 1920 ms 212480 KB Output is correct
14 Correct 2651 ms 215016 KB Output is correct
15 Correct 1203 ms 212052 KB Output is correct
16 Correct 2987 ms 239852 KB Output is correct
17 Correct 2843 ms 216076 KB Output is correct
18 Correct 1217 ms 111704 KB Output is correct
19 Correct 340 ms 111132 KB Output is correct
20 Correct 1107 ms 114980 KB Output is correct
21 Correct 1271 ms 112176 KB Output is correct
22 Correct 2590 ms 217248 KB Output is correct
23 Correct 2385 ms 218448 KB Output is correct
24 Correct 4540 ms 219760 KB Output is correct
25 Correct 4217 ms 222164 KB Output is correct
26 Correct 4136 ms 220544 KB Output is correct
27 Correct 4162 ms 240212 KB Output is correct
28 Correct 1310 ms 218448 KB Output is correct
29 Correct 4344 ms 219700 KB Output is correct
30 Correct 4550 ms 219560 KB Output is correct
31 Correct 4424 ms 219984 KB Output is correct
32 Correct 1307 ms 115428 KB Output is correct
33 Correct 376 ms 111132 KB Output is correct
34 Correct 960 ms 110172 KB Output is correct
35 Correct 824 ms 110168 KB Output is correct
36 Correct 1432 ms 110608 KB Output is correct
37 Correct 1404 ms 110488 KB Output is correct