Submission #683280

#	Time	Username	Problem	Language	Result	Execution time	Memory
683280		whqkrtk04	Factories (JOI14_factories)	C++17	0 / 100	32 ms	848 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> plll;
#define fi first
#define se second
const int INF = 1e9+1;
const ll LLINF = (ll)1e18+1;
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) { for(auto i : v) os << i << " "; os << "\n"; return os; }
template <typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) { os << p.fi << " " << p.se; return os; }

vector<vector<int>> S;
vector<int> P, L, I, O;
vector<ll> D;

int lca(int x, int y) {
    if(L[x] < L[y]) swap(x, y);
    for(int i = 19; i >= 0; i--)
        if(L[S[x][i]] >= L[y])
            x = S[x][i];
    if(x == y) return x;
    for(int i = 19; i >= 0; i--)
        if(S[x][i] != S[y][i])
            x = S[x][i], y = S[y][i];
    return P[x];
}

void make_sparse() {
    //cout << "Make Sparse\n";
    S.resize(P.size(), vector<int>(20));
    for(int i = 0; i < P.size(); i++) S[i][0] = P[i];
    for(int i = 0; i < P.size(); i++)
        for(int j = 1; j < 20; j++)
            S[i][j] = S[S[i][j-1]][j-1];
}

void dfs(int x, int p, ll d, int l, int &cnt, vector<bool> &vis, vector<vector<pii>> &E) {
    if(vis[x]) return;
    vis[x] = true; I[x] = cnt++;
    P[x] = p; D[x] = d; L[x] = l;
    for(auto &i : E[x]) dfs(i.fi, x, d+i.se, l+1, cnt, vis, E);
    O[x] = cnt;
}

ll solve(int x, vector<vector<int>> &E, vector<ll> &DV, vector<ll> &DU, vector<int> &M) {
    ll ans = LLINF;
    for(auto i : E[x]) {
        ans = min(ans, solve(i, E, DV, DU, M));
        DV[x] = min(DV[x], DV[i]); DU[x] = min(DU[x], DU[i]);
    }
    ans = min(ans, DV[x]+DU[x]-2*D[M[x]]);
    return ans;
}

void sort_vertex(vector<int> &vertex) {
    sort(vertex.begin(), vertex.end(), [&](int &a, int &b){ return I[a] < I[b]; });
    vertex.erase(unique(vertex.begin(), vertex.end()), vertex.end());
}

vector<vector<int>> make_tree(vector<int> &X, vector<int> &Y,
                              vector<bool> &V, vector<bool> &U, vector<int> &M) {
    for(auto i : X) M.push_back(i);
    for(auto i : Y) M.push_back(i);
    sort_vertex(M);
    for(int i = 1; i < X.size()+Y.size(); i++) M.push_back(lca(M[i-1], M[i]));
    sort_vertex(M);
    //cout << M;
    sort(X.begin(), X.end()); sort(Y.begin(), Y.end());
    //cout << X << Y;
    for(auto v : M) {
        auto vter = lower_bound(X.begin(), X.end(), v);
        V.push_back(vter != X.end() && *vter == v);
        auto uter = lower_bound(Y.begin(), Y.end(), v);
        U.push_back(uter != Y.end() && *uter == v);
        //V.push_back(find(X.begin(), X.end(), v) != X.end());
        //U.push_back(find(Y.begin(), Y.end(), v) != Y.end());
    }
    vector<int> st;
    vector<vector<int>> E(M.size());
    for(int i = 0; i < M.size(); i++) {
        //cout << i << " " << M[i] << " " << I[M[i]] << " " << O[M[i]] << "\n";
        while(st.size() && (I[M[st.back()]] > I[M[i]] || O[M[st.back()]] <= I[M[i]])) st.pop_back();
        if(st.size()) E[st.back()].push_back(i);
        st.push_back(i);
    }
    return E;
}

void Init(int N, int A[], int B[], int V[]) {
    //cout << "Init\n";
    vector<bool> vis(N, false);
    vector<vector<pii>> E(N);
    for(int i = 0; i < N-1; i++) {
        E[A[i]].push_back({B[i], V[i]});
        E[B[i]].push_back({A[i], V[i]});
    }
    P.resize(N); D.resize(N); L.resize(N);
    I.resize(N); O.resize(N);
    int cnt = 0;
    dfs(0, 0, 0LL, 0, cnt, vis, E);
    //cout << P;
    make_sparse();
}

ll Query(int S, int X[], int T, int Y[]) {
    //cout << "query " << S << " " << T << "\n";
    vector<int> XX(X, X+S), YY(Y, Y+T), M;
    //cout << XX << YY;
    vector<bool> V, U;
    vector<vector<int>> E = make_tree(XX, YY, V, U, M);
    //cout << M << " " << E << V << U;
    vector<ll> DV(E.size(), LLINF), DU(E.size(), LLINF);
    for(int i = 0; i < E.size(); i++) {
        if(V[i]) DV[i] = D[M[i]];
        if(U[i]) DU[i] = D[M[i]];
    }
    return solve(0, E, DV, DU, M);
}

Compilation message (stderr)

factories.cpp: In function 'void make_sparse()':
factories.cpp:37:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for(int i = 0; i < P.size(); i++) S[i][0] = P[i];
      |                    ~~^~~~~~~~~~
factories.cpp:38:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for(int i = 0; i < P.size(); i++)
      |                    ~~^~~~~~~~~~
factories.cpp: In function 'std::vector<std::vector<int> > make_tree(std::vector<int>&, std::vector<int>&, std::vector<bool>&, std::vector<bool>&, std::vector<int>&)':
factories.cpp:71:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for(int i = 1; i < X.size()+Y.size(); i++) M.push_back(lca(M[i-1], M[i]));
      |                    ~~^~~~~~~~~~~~~~~~~~~
factories.cpp:86:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |     for(int i = 0; i < M.size(); i++) {
      |                    ~~^~~~~~~~~~
factories.cpp: In function 'll Query(int, int*, int, int*)':
factories.cpp:119:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |     for(int i = 0; i < E.size(); i++) {
      |                    ~~^~~~~~~~~~

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