oj.uz

답안 #843450

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
843450 2023-09-04T02:40:11 Z hotboy2703 공장들 (JOI14_factories) C++17
15 / 100
 4127 ms 55508 KB 
#include "factories.h"
#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define pii pair<int, int>
#define vi vector<int>
#define vll vector<ll>
#define vvi vector<vi>
#define vii vector<pii>
#define isz(x) (int)x.size()
using namespace std;
 
const int mxN = 5e5 + 5;
const ll oo = 1e18;
 
int n;
vector<vii> G;
 
vi vtn;
//vii -> vll
vector<vector <pair <int,ll> > > vt;
 
ll dis[mxN];
//mxN
pii sparse[19][mxN * 2];
int timer, ecnt, ap[mxN], dep[mxN], cur[mxN], tin[mxN], tout[mxN];
 
void dfs(int v, int p) {
    tin[v] = ++timer;
    dep[v] = dep[p] + 1;
    sparse[0][++ecnt] = {dep[v], v};
    ap[v] = ecnt;
    //dis
    for(auto &[u, w] : G[v]) {
        if(u == p) continue;
        dis[u] = dis[v] + w;
        dfs(u, v);
        sparse[0][++ecnt] = {dep[v], v};
    }
 
    tout[v] = ++timer;
}
 
void build_sparse() {
    for(int p = 1, i = 1; p << 1 <= ecnt; p <<= 1, ++i)
        for(int j = 1; j <= ecnt - (p << 1) + 1; ++j)
            sparse[i][j] = min(sparse[i - 1][j], sparse[i - 1][j + p]);
}
 
bool is_ancestor(int u, int v) {
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}
 
int LCA(int u, int v) {
    int l = ap[u], r = ap[v];
    if(l > r) swap(l, r);
    int len = r - l + 1, lg_len = __lg(len);
    return min(sparse[lg_len][l], sparse[lg_len][r - (1 << lg_len) + 1]).ss;
}
 
void Init(int N, int A[], int B[], int D[]) {
    n = N;
    G.resize(n); vt.resize(n);
    for(int i = 0; i < N - 1; ++i) {
        G[A[i]].emplace_back(B[i], D[i]);
        G[B[i]].emplace_back(A[i], D[i]);
    }
    dfs(0, 0); build_sparse();
}
 
long long Query(int S, int X[], int T, int Y[]) {
    queue<pii> q;
 
    for(int i = 0; i < S; ++i) {
        cur[X[i]] = 1;
        q.emplace(X[i], 0);
        vtn.emplace_back(X[i]);
    }
    for(int i = 0; i < T; ++i) {
        cur[Y[i]] = 2;
        vtn.emplace_back(Y[i]);
    }
 
    sort(all(vtn), [&](int u, int v) {
        return tin[u] < tin[v];
    });
 
    for(int i = 0; i < S + T - 1; ++i) {
        vtn.emplace_back(LCA(vtn[i], vtn[i + 1]));
    }
 
    sort(all(vtn), [&](int u, int v) {
        return tin[u] < tin[v];
    });
    vtn.erase(unique(all(vtn)), vtn.end());
 
    auto add_vt = [&](int u, int v, int w) {
        vt[u].emplace_back(v, w);
        vt[v].emplace_back(u, w);
    };
 
    stack<int> s;
    for(int i = 0; i < isz(vtn); ++i) {
        while(not s.empty() && not is_ancestor(s.top(), vtn[i])) s.pop();
        if(s.empty()) s.emplace(vtn[i]);
        else {
            add_vt(s.top(), vtn[i], dis[vtn[i]] - dis[s.top()]);
            s.emplace(vtn[i]);
        }
    }
 
    ll res = oo;
 
    auto dfs = [&](auto self, int v, int p) -> vll {
        vll cur_dis(2, oo);
        if(cur[v]) cur_dis[cur[v] - 1] = 0;
        //vt, G
        for(auto &[u, w] : vt[v]) {
            if(u == p) continue;
            //cout<<u<<' '<<v<<' '<<w<<' '<<dis[u]<<' '<<dis[v]<<'\n';
            vll tmp = self(self, u, v);
            for(int i = 0; i < 2; ++i)
                cur_dis[i] = min(cur_dis[i], tmp[i] + w);
        }
        res = min(res, accumulate(all(cur_dis), 0LL));
        return cur_dis;
    };
 
    dfs(dfs, vtn[0], 0);
    for (auto x:vtn){
        cur[x] = 0;
        vt[x].clear();
    }
    /*for(int i = 0; i < S; ++i) {
        cur[X[i]] = 0;
        vt[X[i]].clear();
    }
    for(int i = 0; i < T; ++i) {
        cur[Y[i]] = 0;
        vt[Y[i]].clear();
    }
    vtn.clear();*/
 
    return res;
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 41560 KB Output is correct
2 Correct 4051 ms 54720 KB Output is correct
3 Correct 3692 ms 54732 KB Output is correct
4 Correct 3840 ms 54772 KB Output is correct
5 Correct 4127 ms 55508 KB Output is correct
6 Correct 3568 ms 54772 KB Output is correct
7 Correct 3703 ms 54736 KB Output is correct
8 Correct 3839 ms 55120 KB Output is correct
9 Correct 4114 ms 55292 KB Output is correct
10 Correct 3502 ms 54776 KB Output is correct
11 Correct 3689 ms 54864 KB Output is correct

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 25 ms 41560 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 41560 KB Output is correct
2 Correct 4051 ms 54720 KB Output is correct
3 Correct 3692 ms 54732 KB Output is correct
4 Correct 3840 ms 54772 KB Output is correct
5 Correct 4127 ms 55508 KB Output is correct
6 Correct 3568 ms 54772 KB Output is correct
7 Correct 3703 ms 54736 KB Output is correct
8 Correct 3839 ms 55120 KB Output is correct
9 Correct 4114 ms 55292 KB Output is correct
10 Correct 3502 ms 54776 KB Output is correct
11 Correct 3689 ms 54864 KB Output is correct
12 Incorrect 25 ms 41560 KB Output isn't correct
13 Halted 0 ms 0 KB -