Submission #841846

#	Time	Username	Problem	Language	Result	Execution time	Memory
841846		vjudge1	Roadside Advertisements (NOI17_roadsideadverts)	C++17	100 / 100	68 ms	20016 KiB

roadsideadverts

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")

#include <bits/stdc++.h>
 
#define int long long 
#define pb push_back
#define ui unsigned int
#define ld long double
#define pl pair<long long int,  long long int>
#define boost ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ff first    
#define ss second
#define sz size()
#define all(x) x.begin(), x.end()
 
using namespace std;
 
const int maxn = 1e5 + 11;
const int inf = 1e18 + 1;
// const int mod = 1e9 + 7;
const int mod = 998244353;
const int dx[] = {-1, 0, 0, 1, -1, -1, 1, 1};
const int dy[] = {0, -1, 1 , 0, -1, 1, -1, 1};
const double eps = 1e-10;

vector<pair<int, int>> g[maxn];
int tin[maxn], tout[maxn], timer;
int p[maxn][21];
int d[maxn];

void dfs(int v, int pr = 0) {
    tin[ v ] = ++timer;
    p[ v ][ 0 ] = pr;

    for(int k = 1; k <= 20; k++) {
        p[ v ][ k ] = p[p[ v ][k - 1]][k - 1];
    }
    for(auto it : g[ v ]) {
        int to = it.ff;
        int w = it.ss;
        if(to == pr) {
            continue;
        }
        d[ to ] = d[ v ] + w;
        dfs(to, v);
    }
    tout[ v ] = timer;
}
bool cmp(int x, int y) {
    return tin[ x ] < tin[ y ];
}

bool parent(int u, int v) {
    if(!u) {
        return true;
    }

    return tin[ u ] <= tin[ v ] && tout[ u ] >= tout[ v ];
}

int lca(int u, int v) {
    if(parent(u, v)) return u;
    if(parent(v, u)) return v;

    for(int k = 20; k >= 0; k--) {
        if(!parent(p[ v ][ k ], u)) {
            v = p[ v ][ k ];
        }
    }
    return p[ v ][ 0 ];
}

int calc(int x, int y) {
    return d[ x ] + d[ y ] - d[lca(x, y)] - d[lca(x, y)];
}

void solve() {
    int n;

    cin >> n;

    for(int i = 1; i < n; i++) {
        int u, v, w;

        cin >> u >> v >> w;

        u++;
        v++;

        g[ u ].pb({v, w});
        g[ v ].pb({u, w});
    }
    dfs( 1 );

    // for(int i = 1; i <= n; i++) {
    //     cout << d[ i ] << ' ';
    // }
    // cout << "\n";
    int q;

    cin >> q;

    while(q--) {
        int a[ 5 ];

        for(int i = 0; i < 5; i++) {
            cin >> a[ i ];
            a[ i ]++;
        }
        sort(a, a + 5, cmp);

        // for(int i = 0; i < 5; i++) {
        //     cout << a[ i ] << ' ';
        // }
        // cout << "\n";

        int ans = 0;

        for(int i = 0; i < 4; i++) {
            ans += calc(a[ i ], a[i + 1]);
            // cout << calc(a[ i ], a[i + 1]) << ' ' << lca(a[ i ], a[i + 1]) << "\n";
        }
        ans += calc(lca(a[ 0 ], a[ 4 ]), a[ 0 ]);
        // cout << calc(lca(a[ 0 ], a[ 4 ]), a[ 0 ]) << ' ' << lca(a[ 0 ], a[ 4 ]) << "\n";
        ans += calc(lca(a[ 0 ], a[ 4 ]), a[ 4 ]);
        // cout << calc(lca(a[ 0 ], a[ 4 ]), a[ 4 ]) << ' ' << lca(a[ 0 ], a[ 4 ]) << "\n";


        cout << ans / 2 << "\n";
    }
}
    
signed main() {
    // freopen("sum.in", "r", stdin); 
    // freopen("sum.out", "w", stdout);
 
    boost;      

    int tt = 1;

    // cin >> tt;

    for(int i = 1; i <= tt; i++) {
        // cout << "Case " << i << ":\n";
        solve();    
    }           
}

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