Submission #312284

#	Time	Username	Problem	Language	Result	Execution time	Memory
312284		jainbot27	Factories (JOI14_factories)	C++17	0 / 100	8096 ms	768 KiB

factories

#include <bits/stdc++.h>
using namespace std;

#define f first
#define s second
#define pb push_back
#define ar array
#define all(x) x.begin(), x.end()
#define siz(x) (int)x.size()

#define FOR(x, y, z) for(int x = (y); x < (z); x++)
#define ROF(x, z, y) for(int x = (y-1); x >= (z); x--)
#define F0R(x, z) FOR(x, 0, z)
#define R0F(x, z) ROF(x, 0, z)
#define trav(x, y) for(auto&x:y)

using ll = long long;
using vi = vector<int>;
using vl = vector<long long>;
using pii = pair<int, int>;
using vpii = vector<pair<int, int>>;

template<class T> inline bool ckmin(T&a, T b) {return b < a ? a = b, 1 : 0;}
template<class T> inline bool ckmax(T&a, T b) {return b > a ? a = b, 1 : 0;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const char nl = '\n';
const int mxN = 5e5 + 10;
const int MOD = 1e9 + 7;
const long long infLL = 1e18;

struct centroid{
    vector<vector<int>> adj;
    vector<bool> vis;
    vi par, sz;
    int n;
    void init(int _n){ n = _n; adj.resize(n); par.resize(n); sz.resize(n); vis.resize(n, 0);}
    void add(int a, int b) {adj[a].pb(b); adj[b].pb(a);}
    int find_size(int u, int p = -1) {
        if(vis[u]) return 0;
        sz[u] = 1;
        trav(v, adj[u]){
            if(v != p)
                sz[u] += find_size(v, u);
        }
        return sz[u];
    }
    int find_centroid(int u, int p, int N){
        trav(v, adj[u]){
            if(v!=p&&!vis[v]&&sz[v]>N/2)
                return find_centroid(v, u, N);
        }
        return u;
    }
    void init_centroid(int u = 0, int p = -1){
        find_size(u);
        int c = find_centroid(u, -1, sz[u]);
        vis[c] = 1;
        par[c] = p;
        trav(v, adj[c])
            if(!vis[v])
                init_centroid(v, c);
    }
}C;
struct LCA{
    int n, m=0; vl d, depth; vector<ar<int, 25>> anc; vector<vector<pair<int, ll>>> adj;
    void init(int _n){ n = _n; adj.resize(n); d.resize(n, 0LL); depth.resize(n, 0LL); anc.resize(n);}
    void add(int a, int b, ll dist){ adj[a].pb({b, dist}); adj[b].pb({a, dist}); }
    void dfs(int u = 0, int p = -1){
        anc[u][0] = p; FOR(i, 1, 25) {anc[u][i]=(anc[u][i-1]==-1?-1:anc[anc[u][i-1]][i-1]);}
        trav(v, adj[u]){
            if(p == v.f) continue; 
            d[v.f] = d[u] + 1; 
            depth[v.f] = depth[u] + v.s; 
            dfs(v.f, u);
        }
    }
    int lca(int a, int b){
        if(d[a] < d[b]) swap(a, b);
        int dif = d[a] - d[b];
        R0F(i, 25){if(dif&(1<<i)) a = anc[a][i];}
        if(a==b) return a;
        R0F(i, 25){if(anc[a][i] == anc[b][i]) continue;a = anc[a][i]; b = anc[b][i];}
        return anc[a][0];
    }
    ll dist(int a, int b){ int l = lca(a, b); return depth[a]+depth[b]-2*depth[l];}
} L;
int n, q; ll bst[mxN];

void upd(int u, int d){
    int orig = u;
    while(u != -1){
        if(d==1)
            ckmin(bst[u], L.dist(u, orig));
        else 
            bst[u] = infLL;
        u = C.par[u];
    }
}
ll qry(int u){
    int orig = u;
    ll res = infLL;
    while(u != -1){
        ckmin(res, L.dist(u, orig) + bst[u]);
        u = C.par[u];
    }
    return res;
}
void Init(int N, int A[], int B[], int* D){
    n = N;
    L.init(n);
    C.init(n);
    FOR(i, 1, n){
        int e1 = A[i], e2 = B[i]; ll e3 = D[i];
        L.add(e1, e2, e3);
        C.add(e1, e2);
    }
}
ll Query(int S, int x[], int T, int y[]){
    F0R(i, S){
        upd(x[i], 1);
    }
    ll ans = infLL;
    F0R(i, T){
        ckmin(ans, qry(y[i]));
    }
    F0R(i, S){
        upd(x[i], 0);
    }
    return ans;
}
// int32_t main(){
//     ios_base::sync_with_stdio(0); cin.tie(0);
//     cin >> n >> q;
//     C.init(n); L.init(n);
//     FOR(i, 1, n){
//         int e1, e2, e3;
//         cin >> e1 >> e2 >> e3;
//         L.add(e1, e2, e3);
//         C.add(e1, e2);
//     }
//     F0R(i, n) bst[i] = infLL;
//     L.dfs();
//     C.init_centroid();
//     F0R(Q, q){
//         int S, T; cin >> S >> T;
//         vi x(S), y(T);
//         trav(X, x) cin >> X;
//         trav(Y, y) cin >> Y;
//         F0R(i, S){
//             upd(x[i], 1);
//         }
//         ll ans = infLL;
//         F0R(i, T){
//             ckmin(ans, qry(y[i]));
//         }
//         cout << ans << nl;
//         F0R(i, S){
//             upd(x[i], 0);
//         }
//     }
//     return 0;
// }

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