oj.uz

답안 #843490

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
843490 2023-09-04T03:36:41 Z daoquanglinh2007 공장들 (JOI14_factories) C++17
15 / 100
 8000 ms 235088 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 = 1e6 + 5;
const ll oo = 1e18;
 
int n;
vector<vii> G;
 
vi vtn;
vector<vii> vt;
 
ll dis[mxN];
pii sparse[19][mxN];
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;
 
    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() {
	assert(ecnt <= 2*n);
    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);
    int res = min(sparse[lg_len][l], sparse[lg_len][r - (1 << lg_len) + 1]).ss;
    //assert(res > 0);
    return res;
}
 
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;
        for(auto &[u, w] : G[v]) {
            if(u == p) continue;
            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 (int i = 0; i < vtn.size(); i++){
    	vt[vtn[i]].clear();
    	cur[vtn[i]] = 0;
	}
    vtn.clear();
 
    return res;
}

Compilation message

factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:136:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |     for (int i = 0; i < vtn.size(); i++){
      |                     ~~^~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 45660 KB Output is correct
2 Correct 1286 ms 58704 KB Output is correct
3 Correct 1456 ms 58708 KB Output is correct
4 Correct 1442 ms 59080 KB Output is correct
5 Correct 1661 ms 59536 KB Output is correct
6 Correct 781 ms 58708 KB Output is correct
7 Correct 1448 ms 58716 KB Output is correct
8 Correct 1413 ms 58964 KB Output is correct
9 Correct 1602 ms 59532 KB Output is correct
10 Correct 791 ms 58712 KB Output is correct
11 Correct 1464 ms 58716 KB Output is correct

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 45672 KB Output is correct
2 Execution timed out 8050 ms 235088 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 45660 KB Output is correct
2 Correct 1286 ms 58704 KB Output is correct
3 Correct 1456 ms 58708 KB Output is correct
4 Correct 1442 ms 59080 KB Output is correct
5 Correct 1661 ms 59536 KB Output is correct
6 Correct 781 ms 58708 KB Output is correct
7 Correct 1448 ms 58716 KB Output is correct
8 Correct 1413 ms 58964 KB Output is correct
9 Correct 1602 ms 59532 KB Output is correct
10 Correct 791 ms 58712 KB Output is correct
11 Correct 1464 ms 58716 KB Output is correct
12 Correct 12 ms 45672 KB Output is correct
13 Execution timed out 8050 ms 235088 KB Time limit exceeded
14 Halted 0 ms 0 KB -