oj.uz

Submission #764962

# Submission time Handle Problem Language Result Execution time Memory
764962 2023-06-24T07:00:27 Z vjudge1 Roadside Advertisements (NOI17_roadsideadverts) C++17
7 / 100
 87 ms 64504 KB 
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#define ent '\n'
#define all(x) x.begin(), x.end()
#define s second
#define f first
#define pb push_back
typedef long long ll;
using namespace std;
const int maxn = 2e6 + 250;
const int mod = 1e9 + 7;
const int K = 400;
const double Pi = acos(-1.0);
const long double eps = 1e-9;
#define int long long
int a[maxn], pref[maxn];
vector<pair<int,int>>g[maxn];
int tin[maxn], tout[maxn], lev[maxn];
int p[30][maxn];
int timer;
void dfs(int v, int pa = 0) {
    lev[v] = lev[pa]+1;
    tin[v] = timer;
    timer++;
    p[0][v] = pa;
    for(int i = 1;i < 30; i++) {
        p[i][v] = p[i-1][p[i-1][v]];
    }
    for(auto to:g[v]) {
        if(to.f==pa)continue;
            pref[to.f] = pref[v]+to.s;
            dfs(to.f, v);
    }
    tout[v] = timer-1;
}

bool parent(long long u, long long v) {
    if(tin[u] <= tin[v] && tout[u] >= tout[v]) {
        return 1;
    }
    return 0;
}

int lca(long long u, long long v) {
    if(lev[u] < lev[v]) {
        swap(u, v);
    }
    for(long long i = 19; i >= 0; i--) {
        if(lev[u] - (1<<i) >= lev[v]) {
            u = p[i][u];
        }
    }
    if(u == v) return u;
    for(long long i = 19; i >= 0; i--) {
        if(p[i][u] != p[i][v]) {
            u = p[i][u];
            v = p[i][v];
        }
    }
    return p[0][v];
}
void solve() {
    int n, k, sum = 0;
    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);
    cin >> k;
    for(int i = 1;i <= k; i++) {
        int sum = 0;
        for(int j = 1;j <= 5; j++) {
            cin >> a[j];
            a[j]++;
            sum += pref[a[j]];
        }
        for(int j = 1;j <= 5; j++) {
            int mx = 0;
            for(int l = j+1;l <= 5; l++) {
                int x = lca(a[j], a[l]);
                mx = max(mx, pref[x]);
            }
            sum -= mx;
        }
        cout << sum << ent;
    }
}
signed main () {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    // freopen("position.in", "r" , stdin);
    // freopen("position.out", "w", stdout);
    int t = 1;
    // cin >> t;
    for(int i = 1;i <= t; i++) {
        // cout << "Case #" << i << ": ";
        solve();    
    }
}

Compilation message

roadsideadverts.cpp: In function 'void solve()':
roadsideadverts.cpp:64:15: warning: unused variable 'sum' [-Wunused-variable]
   64 |     int n, k, sum = 0;
      |               ^~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 47520 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 87 ms 64504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 53 ms 63304 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 47520 KB Output is correct
2 Incorrect 87 ms 64504 KB Output isn't correct
3 Halted 0 ms 0 KB -