oj.uz

Submission #1045165

# Submission time Handle Problem Language Result Execution time Memory
1045165 2024-08-05T17:53:36 Z karthi222528 Factories (JOI14_factories) C++17
100 / 100
 7596 ms 197304 KB 
#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<pair<int,int>>> adj;
    vector<pair<int,int>> dfs_arr;
    vector<long long> dep,pos,rdep;
    segTree seg;
    void init(int n,vector<vector<pair<int,int>>> &tree){
        this->n = n;
        this->adj = tree;
        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.first!=p){
                dep[c.first] = dep[u] + 1;
                rdep[c.first] = rdep[u] + c.second;
                dfs(c.first,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<pair<int,int>>> adj;
    vector<bool> removed;
    vector<int> sub,par;
    int n;
    void init(int n,vector<vector<pair<int,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.first]){
                build(c.first,cent);
            }
        }
        return;
    }
    int dfs(int u,int p){
        sub[u] = 1;
        for(auto c: adj[u]){
            if(c.first!=p&&!removed[c.first]){
                sub[u] += dfs(c.first,u);
            }
        }
        return sub[u];
    }
    int centroid(int u,int p,int sz){
        for(auto c: adj[u]){
            if(c.first!=p&&!removed[c.first]){
                if(sub[c.first]>sz/2){
                    return centroid(c.first,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<pair<int,int>>> adj(n+1);
    for(int i = 0;i<n-1;i++){
        adj[u[i]].push_back({v[i],l[i]});
        adj[v[i]].push_back({u[i],l[i]});
    }
    lct.init(n,adj);
    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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 16984 KB Output is correct
2 Correct 1658 ms 22460 KB Output is correct
3 Correct 2254 ms 22352 KB Output is correct
4 Correct 2245 ms 27064 KB Output is correct
5 Correct 2319 ms 27448 KB Output is correct
6 Correct 543 ms 27224 KB Output is correct
7 Correct 2217 ms 27472 KB Output is correct
8 Correct 2275 ms 27320 KB Output is correct
9 Correct 2307 ms 27404 KB Output is correct
10 Correct 565 ms 27352 KB Output is correct
11 Correct 2193 ms 27288 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16984 KB Output is correct
2 Correct 3514 ms 164900 KB Output is correct
3 Correct 4465 ms 165160 KB Output is correct
4 Correct 950 ms 171312 KB Output is correct
5 Correct 4497 ms 176476 KB Output is correct
6 Correct 4410 ms 164884 KB Output is correct
7 Correct 4999 ms 48540 KB Output is correct
8 Correct 846 ms 49412 KB Output is correct
9 Correct 4917 ms 50068 KB Output is correct
10 Correct 4964 ms 49124 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 16984 KB Output is correct
2 Correct 1658 ms 22460 KB Output is correct
3 Correct 2254 ms 22352 KB Output is correct
4 Correct 2245 ms 27064 KB Output is correct
5 Correct 2319 ms 27448 KB Output is correct
6 Correct 543 ms 27224 KB Output is correct
7 Correct 2217 ms 27472 KB Output is correct
8 Correct 2275 ms 27320 KB Output is correct
9 Correct 2307 ms 27404 KB Output is correct
10 Correct 565 ms 27352 KB Output is correct
11 Correct 2193 ms 27288 KB Output is correct
12 Correct 7 ms 16984 KB Output is correct
13 Correct 3514 ms 164900 KB Output is correct
14 Correct 4465 ms 165160 KB Output is correct
15 Correct 950 ms 171312 KB Output is correct
16 Correct 4497 ms 176476 KB Output is correct
17 Correct 4410 ms 164884 KB Output is correct
18 Correct 4999 ms 48540 KB Output is correct
19 Correct 846 ms 49412 KB Output is correct
20 Correct 4917 ms 50068 KB Output is correct
21 Correct 4964 ms 49124 KB Output is correct
22 Correct 5042 ms 165052 KB Output is correct
23 Correct 5151 ms 165044 KB Output is correct
24 Correct 7573 ms 164536 KB Output is correct
25 Correct 7508 ms 189628 KB Output is correct
26 Correct 7596 ms 188952 KB Output is correct
27 Correct 7428 ms 197304 KB Output is correct
28 Correct 1380 ms 195888 KB Output is correct
29 Correct 7472 ms 188856 KB Output is correct
30 Correct 7532 ms 188600 KB Output is correct
31 Correct 7488 ms 188712 KB Output is correct
32 Correct 4600 ms 64468 KB Output is correct
33 Correct 855 ms 63412 KB Output is correct
34 Correct 3294 ms 61344 KB Output is correct
35 Correct 3374 ms 61560 KB Output is correct
36 Correct 4900 ms 61504 KB Output is correct
37 Correct 4908 ms 61596 KB Output is correct