Submission #1045154

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045154		karthi222528	Factories (JOI14_factories)	C++17	33 / 100	8035 ms	362108 KiB

factories

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

struct segTree{
    int n;
    int inf = 1e9;
    vector<pair<int,int>> st;
    void init(int n){
        this->n = n;
        st.resize(4*n,{-1,inf});
    }
    pair<int,int> merge_pair(pair<int,int> &p1,pair<int,int> &p2){
        if(p1.second<p2.second){
            return p1;
        }else{
            if(p1.second>p2.second){
                return p2;
            }
            if(p1.first<p2.first){
                return p1;
            }
            return p2;
        }
    }
    void build(int node,int s,int e,vector<pair<int,int>> &v){
        if(s==e){
            st[node] = v[s];
            return;
        }
        int lc = 2*node + 1;
        int rc = lc + 1;
        int mid = s + (e-s)/2;
        build(lc,s,mid,v);
        build(rc,mid+1,e,v);
        st[node] = merge_pair(st[lc],st[rc]);
        return;
    }
    pair<int,int> query_min(int node,int s,int e,int l,int r){
        if(e<l||s>r){
            return {-1,inf};
        }
        if(s>=l&&e<=r){
            return st[node];
        }
        int lc = 2*node + 1;
        int rc = lc + 1;
        int mid = s + (e-s)/2;
        pair<int,int> le = query_min(lc,s,mid,l,r);
        pair<int,int> ri = query_min(rc,mid+1,e,l,r);
        return merge_pair(le,ri);
    }
};
struct lca_tree{
    int n;
    int id = 0;
    vector<vector<int>> adj;
    map<pair<int,int>,int> wei;
    vector<pair<int,int>> dfs_arr;
    vector<long long> dep,pos,rdep;
    segTree seg;
    void init(int n,vector<vector<int>> &tree,map<pair<int,int>,int> &weight){
        this->n = n;
        this->adj = tree;
        this->wei = weight;
        dep.resize(n+1,0);
        rdep.resize(n+1,0);
        pos.resize(n+1,1e9);
        dfs(0,-1);
        seg.init(2*n - 1);
        seg.build(0,0,2*n - 2,dfs_arr);
        pos_assign();
    }
    void dfs(int u,int p){
        dfs_arr.push_back({u,dep[u]});
        for(auto c: adj[u]){
            if(c!=p){
                dep[c] = dep[u] + 1;
                rdep[c] = rdep[u] + wei[{u,c}];
                dfs(c,u);
                dfs_arr.push_back({u,dep[u]});
            }
        }
        return;
    }
    void pos_assign(){
        for(int i = 0;i<2*n - 1;i++){
            pos[dfs_arr[i].first] = min(pos[dfs_arr[i].first],(long long)i);
        }
    }
    int lca(int u,int v){
        int l = min(pos[u],pos[v]);
        int r = max(pos[u],pos[v]);
        pair<int,int> ret = seg.query_min(0,0,2*n - 2,l,r);
        return ret.first;
    }
    int dist(int u,int v){
        int lca_cur = lca(u,v);
        return dep[u] + dep[v] - 2*dep[lca_cur];
    }
    long long len(int u,int v){
        int lca_cur = lca(u,v);
        return rdep[u] + rdep[v] - 2*rdep[lca_cur];
    }
};
struct centroid_decomposition{
    vector<vector<int>> adj;
    vector<bool> removed;
    vector<int> sub,par;
    int n;
    void init(int n,vector<vector<int>> &tree){
        this->n = n;
        this->adj = tree;
        removed.resize(n+1,false);
        sub.resize(n+1);
        par.resize(n+1,-1);
        build(0,-1);
    }
    void build(int u,int p){
        int sz = dfs(u,p);
        int cent = centroid(u,p,sz);
        removed[cent] = true;
        //cout<<cent<<" ";
        par[cent] = p;
        for(auto c: adj[cent]){
            if(!removed[c]){
                build(c,cent);
            }
        }
        return;
    }
    int dfs(int u,int p){
        sub[u] = 1;
        for(auto c: adj[u]){
            if(c!=p&&!removed[c]){
                sub[u] += dfs(c,u);
            }
        }
        return sub[u];
    }
    int centroid(int u,int p,int sz){
        for(auto c: adj[u]){
            if(c!=p&&!removed[c]){
                if(sub[c]>sz/2){
                    return centroid(c,u,sz);
                }
            }
        }
        return u;
    }
};
lca_tree lct;
centroid_decomposition cd;
vector<long long> ans;
void Init(int n,int u[],int v[],int l[]){
    vector<vector<int>> adj(n+1);
    map<pair<int,int>,int> wei;
    for(int i = 0;i<n-1;i++){
        wei[{u[i],v[i]}] = l[i];
        wei[{v[i],u[i]}] = l[i];
        adj[u[i]].push_back(v[i]);
        adj[v[i]].push_back(u[i]);
    }
    lct.init(n,adj,wei);
    cd.init(n,adj);
    ans.resize(n,1e15);
}
long long Query(int s,int c1[],int t,int c2[]){
    for(int i = 0;i<s;i++){
        int node = c1[i];
        while(node!=-1){
            ans[node] = min(ans[node],lct.len(c1[i],node));
            node = cd.par[node];
        }
    }
    long long fans = 1e15;
    for(int i = 0;i<t;i++){
        int node = c2[i];
        while(node!=-1){
            fans = min(fans,lct.len(c2[i],node) + ans[node]);
            node = cd.par[node];
        }
    }
    for(int i = 0;i<s;i++){
        int node = c1[i];
        while(node!=-1){
            ans[node] = 1e15;
            node = cd.par[node];
        }
    }
    return fans;
}

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