oj.uz

Submission #772058

# Submission time Handle Problem Language Result Execution time Memory
772058 2023-07-03T15:02:38 Z Essa2006 Factories (JOI14_factories) C++14
0 / 100
 8000 ms 266336 KB 
#include "factories.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define FF first
#define SS second
#define all(a) a.begin(), a.end()
#define mod (ll)(1000000007)

// #define MAX_N          500000
// #define MAX_Q          100000
// #define MAX_SUM_ST    1000000
// #define MAX_VALUE  1000000000
// static int N, Q;
// static int A[MAX_N], B[MAX_N], D[MAX_N];
// static int S[MAX_N];
// static int T[MAX_N];
// static int X[MAX_SUM_ST];
// static int Y[MAX_SUM_ST];
// static int Qx[MAX_N];
// static int Qy[MAX_N];

const ll inf=1e15, lg=19;
int n;
vector<ll>Dis;
vector<int>dpth;
vector<vector<int>>AA, up;
vector<vector<ll>>Lca;
map<pair<int, int>, ll>mp;

void pre(){ 
    //Dis.clear(), dpth.clear(), AA.clear(), up.clear(), Lca.clear(), mp.clear();
    Dis.resize(n, inf), dpth.resize(n, 2*n), AA.resize(n), up.resize(n, vector<int>(lg+1)), Lca.resize(n, vector<ll>(lg+1));
}

void bfs(int ind){
    queue<int>q;
    q.push(ind);
    up[ind][0]=ind, Lca[ind][0]=0;
    Dis[ind]=dpth[ind]=0;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int j=1;j<=lg;j++){
             up[u][j]=up[up[u][j-1]][j-1];
             Lca[u][j]=min(inf, Lca[u][j-1]+Lca[up[u][j-1]][j-1]);
        }
        for(int i=0;i<AA[u].size();i++){
            int v=AA[u][i];
            if(dpth[u]+1<dpth[v]){
                dpth[v]=dpth[u]+1, Dis[v]=Dis[u]+mp[{u, v}];
                up[v][0]=u, Lca[v][0]=mp[{u, v}];
                q.push(v);
            }
        }
    }
}
ll get_dis(int u, int v){
    // u

    // v
    ll res=0;
    if(dpth[u]>dpth[v])
        swap(u, v);
    for(int j=lg;j>=0;j--){
        if(dpth[up[v][j]]>dpth[u])
            res+=Lca[v][j], v=up[v][j];
    }
    if(dpth[u]!=dpth[v])
        res+=Lca[v][0], v=up[v][0];
    if(u==v)
        return res;
    for(int j=lg;j>=0;j--){
        if(up[u][j]!=up[v][j])
            res+=Lca[u][j]+Lca[v][j], u=up[u][j], v=up[v][j];
    }
    res+=Lca[u][0]+Lca[v][0];
    return res;
}
void Init(int N, int A[], int B[], int D[]) {
    n=N;
    pre();
    for(int i=0;i<n-1;i++){
        int u=A[i], v=B[i], w=D[i];
        AA[u].push_back(v);
        AA[v].push_back(u);
        mp[{u, v}]=mp[{v, u}]=w;
    }
    bfs(0);
}

long long Query(int S, int X[], int T, int Y[]) {
    ll ans=inf;
    for(int i=0;i<S;i++){
        for(int j=0;j<T;j++){
            ans=min(ans, get_dis(X[i], Y[j]));
        }
    }
    return ans;
}

Compilation message

factories.cpp: In function 'void bfs(int)':
factories.cpp:49:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         for(int i=0;i<AA[u].size();i++){
      |                     ~^~~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 816 KB Output is correct
2 Execution timed out 8061 ms 10812 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 596 KB Output is correct
2 Correct 3688 ms 266336 KB Output is correct
3 Execution timed out 8087 ms 263456 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 816 KB Output is correct
2 Execution timed out 8061 ms 10812 KB Time limit exceeded
3 Halted 0 ms 0 KB -