Submission #566644

#	Time	Username	Problem	Language	Result	Execution time	Memory
566644		stevancv	Factories (JOI14_factories)	C++14	100 / 100	4563 ms	364144 KiB

factories

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 5e5 + 2;
const int M = 1e5 + 2;
int mod = 1000000007;
vector<array<int, 2>> g[N];
int sz[N];
bool was[N];
ll mn[N];
void Dfs(int s, int e) {
    sz[s] = 1;
    for (auto u : g[s]) {
        if (u[0] == e || was[u[0]]) continue;
        Dfs(u[0], s);
        sz[s] += sz[u[0]];
    }
}
int Find(int s, int e, int n) {
    for (auto u : g[s]) {
        if (u[0] == e || was[u[0]]) continue;
        if (2 * sz[u[0]] > n) return Find(u[0], s, n);
    }
    return s;
}
int FindCentroid(int node) {
    Dfs(node, -1);
    return Find(node, -1, sz[node]);
}
vector<array<ll, 2>> p[N];
void Solve(int s, int e, int r, ll d) {
    p[s].push_back({r, d});
    for (auto u : g[s]) {
        if (was[u[0]] || u[0] == e) continue;
        Solve(u[0], s, r, d + u[1]);
    }
}
void Decompose(int s) {
    s = FindCentroid(s);
    was[s] = 1;
    Solve(s, -1, s, 0);
    for (auto u : g[s]) {
        if (!was[u[0]]) Decompose(u[0]);
    }
}
void Init(int n, int *a, int *b, int* d) {
    for (int i = 0; i < n - 1; i++) {
        g[a[i]].push_back({b[i], d[i]});
        g[b[i]].push_back({a[i], d[i]});
    }
    Decompose(0);
    for (int i = 0; i < n; i++) mn[i] = 1e18;
}
ll Query(int a, int *x, int b, int *y) {
    vector<int> ch;
    for (int j = 0; j < a; j++) {
        for (auto d : p[x[j]]) {
            smin(mn[d[0]], d[1]);
            ch.push_back(d[0]);
        }
    }
    ll ans = 1e18;
    for (int j = 0; j < b; j++) {
        for (auto d : p[y[j]]) {
            smin(ans, mn[d[0]] + d[1]);
        }
    }
    for (int u : ch) mn[u] = 1e18;
    return ans;
}

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