oj.uz

Submission #1045154

# Submission time Handle Problem Language Result Execution time Memory
1045154 2024-08-05T17:45:48 Z karthi222528 Factories (JOI14_factories) C++17
33 / 100
 8000 ms 362108 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<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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 16984 KB Output is correct
2 Correct 1714 ms 23636 KB Output is correct
3 Correct 2303 ms 23632 KB Output is correct
4 Correct 2298 ms 32580 KB Output is correct
5 Correct 2467 ms 33708 KB Output is correct
6 Correct 609 ms 33104 KB Output is correct
7 Correct 2253 ms 33108 KB Output is correct
8 Correct 2405 ms 33104 KB Output is correct
9 Correct 2456 ms 33708 KB Output is correct
10 Correct 565 ms 33140 KB Output is correct
11 Correct 2290 ms 33360 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 16984 KB Output is correct
2 Correct 4397 ms 285800 KB Output is correct
3 Correct 5731 ms 293340 KB Output is correct
4 Correct 2045 ms 306736 KB Output is correct
5 Correct 5993 ms 362108 KB Output is correct
6 Correct 6033 ms 308664 KB Output is correct
7 Correct 5257 ms 86528 KB Output is correct
8 Correct 972 ms 86200 KB Output is correct
9 Correct 5289 ms 93088 KB Output is correct
10 Correct 5619 ms 86856 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 16984 KB Output is correct
2 Correct 1714 ms 23636 KB Output is correct
3 Correct 2303 ms 23632 KB Output is correct
4 Correct 2298 ms 32580 KB Output is correct
5 Correct 2467 ms 33708 KB Output is correct
6 Correct 609 ms 33104 KB Output is correct
7 Correct 2253 ms 33108 KB Output is correct
8 Correct 2405 ms 33104 KB Output is correct
9 Correct 2456 ms 33708 KB Output is correct
10 Correct 565 ms 33140 KB Output is correct
11 Correct 2290 ms 33360 KB Output is correct
12 Correct 5 ms 16984 KB Output is correct
13 Correct 4397 ms 285800 KB Output is correct
14 Correct 5731 ms 293340 KB Output is correct
15 Correct 2045 ms 306736 KB Output is correct
16 Correct 5993 ms 362108 KB Output is correct
17 Correct 6033 ms 308664 KB Output is correct
18 Correct 5257 ms 86528 KB Output is correct
19 Correct 972 ms 86200 KB Output is correct
20 Correct 5289 ms 93088 KB Output is correct
21 Correct 5619 ms 86856 KB Output is correct
22 Correct 7183 ms 309668 KB Output is correct
23 Correct 7613 ms 310020 KB Output is correct
24 Execution timed out 8035 ms 314868 KB Time limit exceeded
25 Halted 0 ms 0 KB -