Submission #1234016

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234016		Geforgs	Roadside Advertisements (NOI17_roadsideadverts)	C++20	7 / 100	212 ms	24556 KiB

roadsideadverts

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <unordered_map>
#include <stack>
#include <bitset>
#include <string>
#include <cstring>
#include <iterator>
#include <random>
#define ll long long
#define ld long double
#define inf (ll)(2*1e18)
#define sort(a) sort(a.begin(), a.end())
#define reverse(a) reverse(a.begin(), a.end())
#define pb push_back
#define endl "\n"
using namespace std;

const ll dim = 20;

void DFS(ll id, ll last, ll weight, ll d, vector<vector<pair<ll, ll>>>& a, vector<vector<pair<ll, ll>>>& up, vector<ll>& depth){
    up[id][0] = {last, weight};
    depth[id] = d;
    for(int i=1;i<dim;++i){
        up[id][i] = {up[up[id][i-1].first][i-1].first, up[up[id][i-1].first][i-1].second + up[id][i-1].second};
    }
    for(auto [el, w]: a[id]){
        if(el == last) continue;
        DFS(el, id, w, d+1, a, up, depth);
    }
}

pair<ll, ll> lca(ll x, ll y, vector<vector<pair<ll, ll>>>& up, vector<ll>& depth){
    if(depth[x] < depth[y]){
        swap(x, y);
    }
    ll res=0;
    for(int i=19;i>=0;--i){
        if(depth[up[x][i].first] >= depth[y]){
            res += up[x][i].second;
            x = up[x][i].first;
        }
    }
    for(int i=19;i>=0;--i){
        if(up[x][i].first != up[y][i].first){
            res += up[x][i].second;
            res += up[y][i].second;
            x = up[x][i].first;
            y = up[y][i].first;
        }
    }
    if(x == y) return {x, res};
    res += up[x][0].second;
    res += up[y][0].second;
    return {up[x][0].first, res};
}

void solve(){
    ll n, q, i, j, x, y, w, res;
    cin>>n;
    vector<vector<pair<ll, ll>>> a(n);
    vector<vector<pair<ll, ll>>> up(n, vector<pair<ll, ll>>(dim));
    vector<ll> depth(n);
    vector<bool> visited(n, false);
    for(i=1;i<n;++i){
        cin>>x>>y>>w;
        a[x].pb({y, w});
        a[y].pb({x, w});
    }
    DFS(0, 0,  0, 0, a, up, depth);
    cin>>q;
    for(i=0;i<q;++i){
        vector<ll> que(5);
        set<ll> que2;
        for(j=0;j<5;++j){
            cin>>que[j];
            que2.insert(que[j]);
            visited[que[j]] = true;
        }
        map<ll, vector<ll>> children;
        w = que[0];
        res = 0;
        while(!que2.empty()){
            x = *que2.begin();
            que2.erase(que2.begin());
            y = x;
            for(j=0;j<que.size();++j){
                auto p =  lca(x, que[j], up, depth);
                if((depth[y] < depth[p.first] or x == y) and p.first != x){
                    y = p.first;
                }
            }
            if(depth[x] < depth[w]){
                w = x;
            }
            res += lca(x, y, up, depth).second;
            if(x != y){
                children[y].pb(x);
                if(!visited[y]) que2.insert(y), visited[y] = true, cout<<y<<endl;
            }
        }
        cout<<res<<endl;
        for(j=0;j<5;++j){
            visited[que[j]] = false;
        }
        for(auto el: children){
            visited[el.first] = false;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    srand(time(nullptr));
    ll t=1;
//    cin>>t;
    for(;t>0;--t){
        solve();
    }
    return 0;
}

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