oj.uz

Submission #25538

# Submission time Handle Problem Language Result Execution time Memory
25538 2017-06-23T00:31:29 Z kajebiii Factories (JOI14_factories) C++14
100 / 100
 5646 ms 161096 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 125512 KB Output is correct
2 Correct 366 ms 125776 KB Output is correct
3 Correct 453 ms 125776 KB Output is correct
4 Correct 413 ms 125776 KB Output is correct
5 Correct 503 ms 125728 KB Output is correct
6 Correct 323 ms 125812 KB Output is correct
7 Correct 389 ms 125776 KB Output is correct
8 Correct 483 ms 125776 KB Output is correct
9 Correct 403 ms 125728 KB Output is correct
10 Correct 336 ms 125812 KB Output is correct
11 Correct 433 ms 125776 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 125512 KB Output is correct
2 Correct 2866 ms 144256 KB Output is correct
3 Correct 4003 ms 146328 KB Output is correct
4 Correct 773 ms 145224 KB Output is correct
5 Correct 4766 ms 161096 KB Output is correct
6 Correct 4696 ms 146016 KB Output is correct
7 Correct 1456 ms 129588 KB Output is correct
8 Correct 543 ms 129744 KB Output is correct
9 Correct 1469 ms 131676 KB Output is correct
10 Correct 1479 ms 129512 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 3166 ms 144256 KB Output is correct
2 Correct 3013 ms 144256 KB Output is correct
3 Correct 5209 ms 145596 KB Output is correct
4 Correct 4796 ms 146024 KB Output is correct
5 Correct 4656 ms 145924 KB Output is correct
6 Correct 5646 ms 156768 KB Output is correct
7 Correct 1299 ms 145224 KB Output is correct
8 Correct 5479 ms 145648 KB Output is correct
9 Correct 5269 ms 145444 KB Output is correct
10 Correct 5133 ms 145676 KB Output is correct
11 Correct 1409 ms 131676 KB Output is correct
12 Correct 389 ms 129744 KB Output is correct
13 Correct 696 ms 129208 KB Output is correct
14 Correct 909 ms 129208 KB Output is correct
15 Correct 959 ms 129512 KB Output is correct
16 Correct 1323 ms 129512 KB Output is correct