Submission #978546

#	Time	Username	Problem	Language	Result	Execution time	Memory
978546		tnknguyen_	Factories (JOI14_factories)	C++14	0 / 100	318 ms	524288 KiB

factories

#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
#define endl '\n' 
#define ll long long 
#define len(s) (int)s.size() 
#define pii pair<int, int>
//#define int long long 

const int MX = 5e5 + 5;
const int LG = 19;
vector<pii> gr[MX];
ll up[LG][MX], f[LG][MX], dep[MX];
int n, q;

void dfs(int u, int p)  {
    dep[u] = dep[p] + 1, up[0][u] = p;
    for(int j=1; j<LG; ++j){
        up[j][u] = up[j-1][up[j-1][u]];
        f[j][u] = f[j-1][u] + f[j-1][up[j-1][u]];
    }

    for(pii e : gr[u]){
        int v, c;
        tie(v, c) = e;
        if(v != p){
            f[0][v] = c;
            dfs(v, u);
        }
    }
}

ll dist(int u, int v){
    if(dep[u] < dep[v]) { swap(u, v); }

    ll ans = 0;
    for(int j=LG-1; j>=0; --j){
        if(dep[up[j][u]] >= dep[v]){
            ans += f[j][u];
            u = up[j][u];
        }
    }

    if(u == v) { return ans; }

    for(int j=LG-1; j>=0; --j){
        if(up[j][u] != up[j][v]){
            ans += f[j][u] + f[j][v];
            u = up[j][u], v = up[j][v];
        }
    }
    return ans + f[0][u] + f[0][v];
}

ll solve(int u, int p, ll sum, ll &ans, const vector<int> &vi){
    if(vi[u]){
        ans = min(ans, sum);
    }
    for(pii e : gr[u]){
        int v, c;
        tie(v, c) = e;
        solve(v, u, sum + c, ans, vi);
    }
}

void Init(int N, int A[], int B[], int D[]){
    n = N;
    for(int i=0; i<n; ++i){
        int u = A[i], v = B[i], c = D[i];
        ++u, ++v;
        gr[u].push_back({v, c});
        gr[v].push_back({u, c});
    }

    dfs(1, 1);
}

ll Query(int S, int X[], int T, int Y[]){
    ll ans = 1e18;

    vector<int> vi(n + 5);
    for(int i=0; i<T; ++i){ vi[Y[i] + 1] = 1; }

    for(int i=0; i<S; ++i){
        for(int j=0; j<T; ++j){
            // ans = min(ans, dist(X[i], Y[j]));
            solve(X[i]+1, 0, 0, ans, vi);
        }
    }
    return ans;
}

Compilation message (stderr)

factories.cpp: In function 'long long int solve(int, int, long long int, long long int&, const std::vector<int>&)':
factories.cpp:64:1: warning: no return statement in function returning non-void [-Wreturn-type]
   64 | }
      | ^

• Subtask 1: 0 / 15
• Subtask 2: 0 / 18
• Subtask 3: 0 / 67