Submission #25538

#	Time	Username	Problem	Language	Result	Execution time	Memory
25538		kajebiii	Factories (JOI14_factories)	C++14	100 / 100	5646 ms	161096 KiB

factories

#include "factories.h"
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <tuple>

using namespace std;

#define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define REPO(i,n) for(int (i)=1; (i)<=(int)(n); (i)++)
#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<int, int> pi;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF;

const int MAX_N = 5e5 + 100, LOG_N = 20;

int N; bool cChk[MAX_N];
vector<pi> Ed[MAX_N];
int S[MAX_N];
int getS(int v, int p) {
    S[v] = 1;
    for(pi &e : Ed[v]) {
        int w, d; tie(w, d) = e;
        if(w == p || cChk[w]) continue;
        S[v] += getS(w, v);
    }
    return S[v];
}
int findC(int v, int p, int all) {
    for(pi &e : Ed[v]) {
        int w, d; tie(w, d) = e;
        if(w == p || cChk[w]) continue;
        if(S[w] > all / 2) return findC(w, v, all);
    }
    return v;
}

int D[MAX_N], cP[MAX_N]; ll Len[LOG_N][MAX_N];
void getLen(int v, int p, int dep, ll dis) {
    Len[dep][v] = dis;
//    printf("%d %d = %lld\n", dep, v, dis);
    for(pi &e : Ed[v]) {
        int w, d; tie(w, d) = e;
        if(w == p || cChk[w]) continue;
        getLen(w, v, dep, dis+d);
    }
}
int cDfs(int v, int dep) {
    v = findC(v, 0, getS(v, 0));
    D[v] = dep;
    cChk[v] = true;
    getLen(v, 0, dep, 0ll);
//    printf("%d(th) : %d (%d)\n", dep, v, S[v]);
    for(pi &e : Ed[v]) {
        int w, d; tie(w, d) = e;
        if(cChk[w]) continue;
        cP[cDfs(w, dep+1)] = v;
    }
    return v;
}
void Init(int n, int a[], int b[], int d[]) {
    N = n;
    REP(i, N-1) {
        a[i]++; b[i]++;
        Ed[a[i]].push_back(pi(b[i], d[i]));
        Ed[b[i]].push_back(pi(a[i], d[i]));
    }
    cDfs(1, 0);
}

int lastQ[MAX_N], Q; ll minQ[MAX_N];
long long Query(int S, int X[], int T, int Y[]) {
    Q++;
    REP(i, S) {
        int s = X[i] + 1;
        for(int v = s, d = D[v]; v; v = cP[v], d--)
            if(lastQ[v] != Q || minQ[v] > Len[d][s])
                lastQ[v] = Q, minQ[v] = Len[d][s];
    }
    ll ans = LINF;
    REP(i, T) {
        int t = Y[i] + 1;
        for(int v = t, d = D[v]; v; v = cP[v], d--)
            if(lastQ[v] == Q) {
                ans = min(ans, minQ[v] + Len[d][t]);
            }
    }
    return ans;
}

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