Submission #1138900

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138900		agrim_09	Roadside Advertisements (NOI17_roadsideadverts)	C++20	30 / 100	83 ms	31304 KiB

roadsideadverts

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template <class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define endl '\n';
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define py cout << "YES" << endl;
#define pn cout << "NO" << endl;
#define pb push_back
#define int long long
typedef long double lld;
#define double lld
typedef long long ll;
typedef unsigned long long ull;
const ll inf = 1e18;
const ll mod = 1e9+7;
const int N = 2e5;
vector<int>primes = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};

// Check for queue, priorioty_queue, stack, ordered_set solutions
// stack => LIFO (whatever goes in last comes out last)
// queue => FIFO (whatever goes in first comes out first)
// priority_queue => Dynamic queries of minimum/maximum
// ordered_set => set in vector form
//[order_of_key(k) gives number of elements less than k, while find_by_order(i) gives i^th element]

// To comment multiple lines : ctrl + /
// To find and replace : ctrl+H

void judge(){
    srand(time(NULL));
    #ifndef ONLINE_JUDGE
    freopen("1.txt","r",stdin);
    freopen("2.txt","w",stdout);
    freopen("Error.txt", "w", stderr);
    #define debug(x...) cerr << #x <<" = "; _print(x); cerr << endl;
    #else
    #define debug(x...)
    #endif
}

void usaco(string s) {
    freopen((s + ".in").c_str(),"r",stdin);
    freopen((s + ".out").c_str(),"w",stdout);
}

struct bin_node{
    int vertex;
    int dist = 0;
    int val = 0;
    // The other stuff like max

    bool operator==(const bin_node &b){
        return vertex==b.vertex;
    }
};

bin_node unite(bin_node a, bin_node b){ // Order is very imp
    bin_node ans;
    ans.vertex = b.vertex;
    ans.dist = a.dist + b.dist;
    ans.val = a.val + b.val;
    return ans;
}

// Root is 0
class BinaryJump{
    vector<vector<bin_node>>up; vector<int>depth; int n;
    vector<int>par;
    private:
        void build(vector<int>&par){
            int mx = log2(n) + 2;
            //Base Case : 
            for(int i = 0;i<mx;i++){
                up[0][i].vertex = -1;
            }
            for(int i = 1;i<n;i++){
                up[i][0].vertex = par[i];
                up[i][0].dist = 1;
            }
            // Jumps 
            for(int j = 1;j<mx;j++){
                for(int i = 1;i<n;i++){
                    bin_node parent = up[i][j-1];
                    if(parent.vertex==-1){
                        up[i][j].vertex = -1;
                    }
                    else{
                        up[i][j] = unite(parent,up[parent.vertex][j-1]);
                    }
                }
            }
        }

        bin_node kthAncestor(int node, int k){
            if(k>n){
                bin_node ans; ans.vertex = -1;
                return ans;
            }
            bin_node ans; 
            ans.vertex = node;
            while(true){
                if(k==0 or ans.vertex==-1){
                    return ans;
                }
                int p = log2(k);
                ans = unite(ans,up[ans.vertex][p]);
                k -= (1<<p);
            }
        }

        void calc_depth(int node){
            if(depth[node]!=-1){
                return;
            }
            if(node==0){
                depth[node] = 0; return;
            }
            calc_depth(par[node]);
            depth[node] = depth[par[node]] + 1;
        }

        bin_node calc_lca(int a, int b){
            if(depth[a]>depth[b]){
                swap(a,b);
            }
            bin_node x,y;
            // Bring to same depth
            x = kthAncestor(a,0);
            y = kthAncestor(b,depth[b]-depth[a]);
            bin_node ans = x;
            ans = unite(ans,y);
            if(x==y){
                return y;
            }
            // Loop over the i
            for(int i = log2(n)+1;i>=0;i--){
                auto p = kthAncestor(x.vertex,(1<<i));
                auto q = kthAncestor(y.vertex,(1<<i));
                if(p==q){
                    continue;
                }
                else{
                    ans = unite(ans,p);
                    ans = unite(ans,q);
                    x = p; y = q;
                }
            }
            ans = unite(ans,kthAncestor(x.vertex,1));
            ans = unite(ans,kthAncestor(y.vertex,1));
            return ans;
        }

    public:
        BinaryJump(vector<int>&parent, vector<int>&wt){
            par = parent;
            n = par.size();
            int mx = log2(n)+2;
            up.resize(n,vector<bin_node>(mx));
            for(int i = 1;i<n;i++){
                up[i][0].val = wt[i];
            }
            build(par);
            depth.resize(n,-1);
            for(int i = 0;i<n;i++){
                calc_depth(i);
            }
        }
        bin_node kth(int node, int k){
            return kthAncestor(node,k);
        }
        bin_node lca(int a, int b){
            return calc_lca(a,b);
        }
        int deep(int a){
            return depth[a];
        }
};

void dfs(int node, vector<vector<pair<int,int>>>&adj, vector<int>&par, vector<int>&wt){
    for(auto [child,w] : adj[node]){
        if(child==par[node]){
            continue;
        }
        par[child] = node;
        wt[child] = w;
        dfs(child,adj,par,wt);
    }
}

signed main(){
    fastio; //judge();
    int n; cin >> n;
    vector<vector<pair<int,int>>>adj(n);
    for(int i = 0,u,v,w;i<n-1;i++){
        cin >> u >> v >> w;
        adj[u].pb({v,w}); adj[v].pb({u,w});
    }
    vector<int>par(n),wt(n);
    par[0] = -1;
    dfs(0,adj,par,wt);
    BinaryJump p(par,wt);

    int q; cin >> q;
    while(q--){
        vector<int>v(5);
        for(auto &x : v) cin >> x;
        int answer = 0;
        vector<pair<int,int>>depths(5);
        for(int i = 0;i<5;i++){
            depths[i] = {p.deep(v[i]),v[i]};
        }
        set<int>vertices;
        sort(depths.rbegin(),depths.rend());
        
        // Remove stuf lying in same line from root 
        for(int i = 0;i<5;i++){
            bool yes = true;
            for(int j = i+1;j<5;j++){
                bin_node x = p.lca(depths[i].second,depths[j].second);
                if(x.vertex==depths[j].second){
                    yes = false;
                    answer += x.val;
                    //cout << depths[i].second << ' ' << depths[j].second << ' ' << answer << endl;
                    break;
                }
            }
            if(yes){
                //cout << depths[i].second << endl;
                vertices.insert(depths[i].second);
            }
        }
        // No 2 lie in the same line
        while(true){
            if(vertices.size()==1){
                break;
            }
            auto it1 = vertices.begin();
            auto it2 = vertices.end();
            it2--;
            vertices.erase(it1); vertices.erase(it2);
            int u = *it1, v = *it2;
            bin_node x = p.lca(u,v);
            answer += x.val;
            vertices.insert(x.vertex);
        }
        cout << answer << endl;
    }   
}

Compilation message (stderr)

roadsideadverts.cpp: In function 'void judge()':
roadsideadverts.cpp:37:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     freopen("1.txt","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~
roadsideadverts.cpp:38:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |     freopen("2.txt","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~
roadsideadverts.cpp:39:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |     freopen("Error.txt", "w", stderr);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
roadsideadverts.cpp: In function 'void usaco(std::string)':
roadsideadverts.cpp:47:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |     freopen((s + ".in").c_str(),"r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
roadsideadverts.cpp:48:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |     freopen((s + ".out").c_str(),"w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 0 / 40
• Subtask 4: 0 / 30