Submission #473047

#	Time	Username	Problem	Language	Result	Execution time	Memory
473047		ljuba	Factories (JOI14_factories)	C++17	100 / 100	4859 ms	235992 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>

using namespace std;

const int mxN = 600012;

typedef long long ll;

vector<pair<int, ll>> adj[mxN];
bool vis[mxN];
int sub[mxN];

int dfsSize(int s, int p = -1) {
    sub[s] = 1;
    for(auto b : adj[s]) {
        int e = b.first;
        if(e == p || vis[e])
            continue;
        dfsSize(e, s);
        sub[s] += sub[e];
    }
    return sub[s];
}

int centroid(int s, int p, int n) {
    for(auto b : adj[s]) {
        int e = b.first;
        if(e == p || vis[e])
            continue;

        if(sub[e] > n/2)
            return centroid(e, s, n);
    }

    return s;
}

vector<ll> dist[mxN];

void dfs(int s, int p = -1) {
    ll vrednost = 0;
    for(auto b : adj[s]) {
        int e = b.first;
        if(e == p) {
            vrednost = b.second;
            break;
        }
    }
    if(p == -1) {
        dist[s].push_back(0);
    } else {
        dist[s].push_back(vrednost + dist[p].back());
    }
    for(auto b : adj[s]) {
        int e = b.first;
        if(e == p || vis[e])
            continue;
        dfs(e, s);
    }
}

int iznad[mxN];

void build(int s, int p = -1) {
    int n = dfsSize(s);
    int c = centroid(s, -1, n);

    dfs(c, -1);
    iznad[c] = p;
    vis[c] = true;

    for(auto b : adj[c]) {
        int e = b.first;
        if(vis[e])
            continue;
        build(e, c);
    }
}

ll mini[mxN];

void Init(int N, int A[], int B[], int D[]) {
    for(int i = 0; i < N-1; ++i) {
        int u = A[i], v = B[i];
        ll w = D[i];
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    build(0);

    for(int i = 0; i < N; ++i) reverse(dist[i].begin(), dist[i].end());

    for(int i = 0; i < N; ++i)
        mini[i] = LLONG_MAX;
}

long long Query(int S, int X[], int T, int Y[]) {
    //drzi za prve, za druge samo proveri
    ll ans = LLONG_MAX;
    for(int i = 0; i < S; ++i) {
        int trenutni = X[i];
        for(int j = trenutni, cnt = 0; j != -1; j = iznad[j], ++cnt) {
            mini[j] = min(mini[j], dist[trenutni][cnt]);
        }
    }

    for(int i = 0; i < T; ++i) {
        int trenutni = Y[i];
        for(int j = trenutni, cnt = 0; j != -1; j = iznad[j], ++cnt) {
            if(mini[j] == LLONG_MAX) {
                continue;
            }
            ans = min(ans, mini[j] + dist[trenutni][cnt]);
        }
    }

    for(int i = 0; i < S; ++i) {
        int trenutni = X[i];
        for(int j = trenutni, cnt = 0; j != -1; j = iznad[j], ++cnt) {
            mini[j] = LLONG_MAX;
        }
    }

    return ans;
}

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