Submission #521428

#	Time	Username	Problem	Language	Result	Execution time	Memory
521428		AJ00	Roadside Advertisements (NOI17_roadsideadverts)	C++14	100 / 100	60 ms	11820 KiB

roadsideadverts

#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
vector<pair<int,int>> cur;
int ans;
vector<vector<pair<int,ll>>> adj(50000);
struct LCA{
    vector<int> height, first, euler,segtree,dist;
    vector<bool> visited;
    LCA (int n, int root){
        height.resize(n);
        first.resize(n);
        dist.resize(n);
        dist[root] = 0;
        visited.resize(n, false);
        dfs(0,-1,0);
        int m = euler.size();
        segtree.resize(4*m);
        build(1,0,m-1);
    }
    void dfs(int node,int par, int h){
        height[node] = h;
        first[node] = euler.size();
        visited[node] = true;
        euler.push_back(node);
        for (auto pai: adj[node]){
            if (!visited[pai.first] && pai.first != par){
                dist[pai.first] = dist[node]+pai.second;
                dfs(pai.first,node,h+1);
                euler.push_back(node);
            }
        }
    }
    void printall(int n){
        for (int i = 0; i < n; i++){
            cout << first[i] << " ";
        }
        cout << "\n";
        for (int i = 0; i < n; i++){
            cout << height[i] << " ";
        }
        cout << "\n";
        for (int i = 0; i < n; i++){
            cout << dist[i] << " ";
        }
        cout << "\n";
        for (int i = 0; i < euler.size(); i++){
            cout << euler[i] << " ";
        }
        cout << "\n";
        for (int i = 0; i < segtree.size(); i++){
            cout << segtree[i] << " ";
        }
    }
    void build(int pos, int l, int r){
        if (l == r){
            segtree[pos] = euler[l];
            return;
        }
        int mid = (l+r)/2;
        build(pos*2, l,mid);
        build((pos*2)+1,mid+1,r);
        int x = segtree[pos*2];
        int y = segtree[(pos*2)+1];
        segtree[pos] =  height[x] < height[y] ? x : y;
        return;
    }
    int query(int pos, int l, int r, int ql, int qr){
        if (ql > r || l > qr){
            return -1;    
        }    
        if (ql <= l && qr >= r){
            return segtree[pos];
        }
        int mid = (l+r)/2;
        int left = query(pos*2, l,mid,ql,qr);
        int right = query((pos*2)+1, mid+1, r, ql,qr);
        if (left == -1){
            return right;
        }
        if (right == -1){
            return left;
        }
        return height[left] < height[right] ? left : right;
    }
    int findfirst(int x){
        return first[x];
    }
    int findlca(int u, int v){
        u = first[u];
        v = first[v];
        if (u > v){
            swap(u,v);
        }
        return query(1,0,euler.size()-1,u,v);
    }
    int finddist(int u, int v){
        return dist[u]+dist[v]-(2*dist[findlca(u,v)]);
    }
};
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t=1,n,u,v,q,a,b,c,d,e; 
    ll w;
    //cin >> t; 
    while (t--){
        cin >> n;
        for (int i = 0; i < n-1; i++){
            cin >> u >> v >> w;
            adj[u].emplace_back(v,w);
            adj[v].emplace_back(u,w);
        }
        LCA lca(n,0);
        cin >> q;
      //  lca.printall(n);
        for (int i = 0; i < q; i++){
            cin >> a >> b >> c >> d >> e;
            ans = 0;
            cur.clear();
          //  vector<bool> special(n,false);
         //   vector<bool> visited(n,false);
            cur.emplace_back(lca.findfirst(a),a);
            cur.emplace_back(lca.findfirst(b),b);
            cur.emplace_back(lca.findfirst(c),c);
            cur.emplace_back(lca.findfirst(d),d);
            cur.emplace_back(lca.findfirst(e),e);
            sort(cur.begin(),cur.end());
            /*for (int i = 0; i < 5; i++){
                cout << cur[i].first << " " << cur[i].second << "\n";
            }
            cout << "\n";*/
            for (int i = 0; i < 4; i++){
                ans += lca.finddist(cur[i].second, cur[i+1].second);
            }
           // cout << "\n";
            ans += lca.finddist(cur[4].second, cur[0].second);
            ans /= 2;
            cout << ans << "\n";
        }
    }
    return 0;
}

Compilation message (stderr)

roadsideadverts.cpp: In member function 'void LCA::printall(int)':
roadsideadverts.cpp:47:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         for (int i = 0; i < euler.size(); i++){
      |                         ~~^~~~~~~~~~~~~~
roadsideadverts.cpp:51:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         for (int i = 0; i < segtree.size(); i++){
      |                         ~~^~~~~~~~~~~~~~~~

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