oj.uz

Submission #752476

# Submission time Handle Problem Language Result Execution time Memory
752476 2023-06-03T04:44:37 Z 12345678 Roadside Advertisements (NOI17_roadsideadverts) C++17
100 / 100
 106 ms 11020 KB 
#include <bits/stdc++.h>

using namespace std;

const int nx=5e4+5, lx=17;
int n, u, v, w, pa[nx][lx], lvl[nx], ds[nx], l[6], q, tn;
vector<vector<pair<int, int>>> d(nx);

void dfs(int u, int p)
{
    lvl[u]=lvl[p]+1;
    pa[u][0]=p;
    for (int i=1; i<lx; i++) pa[u][i]=pa[pa[u][i-1]][i-1];
    for (auto [v, w]:d[u]) if (v!=p) ds[v]=ds[u]+w, dfs(v, u);
}

int lca(int u, int v)
{
    if (lvl[u]>lvl[v]) swap(u, v);
    for (int i=lx-1; i>=0; i--) if (lvl[pa[v][i]]>=lvl[u]) v=pa[v][i];
    if (u==v) return v;
    for (int i=lx-1; i>=0; i--) if (pa[u][i]!=pa[v][i]) u=pa[u][i], v=pa[v][i];
    return pa[u][0];
}

int dist(int u, int v)
{
    return ds[u]+ds[v]-ds[lca(u, v)];
}

bool cmp(int a, int b)
{
    return lvl[a]<=lvl[b];
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n; lvl[n]=1e9;
    for (int i=0; i<n-1; i++) cin>>u>>v>>w, d[u].push_back({v, w}), d[v].push_back({u, w});
    dfs(0, 0);
    cin>>q;
    while (q--)
    {
        for (int i=0; i<5; i++) cin>>l[i];
        sort(l, l+5, cmp);
        int tn=n, ans=0;
        for (int i=1; i<5; i++)
        {
            int cn=lca(l[0], l[i]);
            if (lvl[cn]<lvl[tn]) tn=cn;
        }
        for (int i=0; i<5; i++)
        {
            int mn=ds[l[i]]-ds[tn];
            for (int j=0; j<i; j++) mn=min(mn, ds[l[i]]-ds[lca(l[i], l[j])]);
            ans+=mn;
        }
        cout<<ans<<'\n';
    }
}

Subtask #1
7.0 / 7.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 9548 KB Output is correct
2 Correct 71 ms 10948 KB Output is correct
3 Correct 85 ms 11020 KB Output is correct
4 Correct 65 ms 11016 KB Output is correct
5 Correct 65 ms 10960 KB Output is correct
6 Correct 74 ms 11000 KB Output is correct
7 Correct 66 ms 11008 KB Output is correct
8 Correct 98 ms 11004 KB Output is correct
9 Correct 79 ms 11020 KB Output is correct
10 Correct 60 ms 10940 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 7756 KB Output is correct
2 Correct 34 ms 10092 KB Output is correct
3 Correct 32 ms 10188 KB Output is correct
4 Correct 34 ms 10100 KB Output is correct
5 Correct 33 ms 10140 KB Output is correct
6 Correct 30 ms 10160 KB Output is correct
7 Correct 32 ms 10148 KB Output is correct
8 Correct 41 ms 10088 KB Output is correct
9 Correct 49 ms 10188 KB Output is correct
10 Correct 31 ms 10060 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 76 ms 9548 KB Output is correct
3 Correct 71 ms 10948 KB Output is correct
4 Correct 85 ms 11020 KB Output is correct
5 Correct 65 ms 11016 KB Output is correct
6 Correct 65 ms 10960 KB Output is correct
7 Correct 74 ms 11000 KB Output is correct
8 Correct 66 ms 11008 KB Output is correct
9 Correct 98 ms 11004 KB Output is correct
10 Correct 79 ms 11020 KB Output is correct
11 Correct 60 ms 10940 KB Output is correct
12 Correct 30 ms 7756 KB Output is correct
13 Correct 34 ms 10092 KB Output is correct
14 Correct 32 ms 10188 KB Output is correct
15 Correct 34 ms 10100 KB Output is correct
16 Correct 33 ms 10140 KB Output is correct
17 Correct 30 ms 10160 KB Output is correct
18 Correct 32 ms 10148 KB Output is correct
19 Correct 41 ms 10088 KB Output is correct
20 Correct 49 ms 10188 KB Output is correct
21 Correct 31 ms 10060 KB Output is correct
22 Correct 67 ms 9484 KB Output is correct
23 Correct 72 ms 8132 KB Output is correct
24 Correct 69 ms 10484 KB Output is correct
25 Correct 81 ms 10576 KB Output is correct
26 Correct 62 ms 10544 KB Output is correct
27 Correct 61 ms 10496 KB Output is correct
28 Correct 61 ms 10452 KB Output is correct
29 Correct 106 ms 10532 KB Output is correct
30 Correct 63 ms 10436 KB Output is correct
31 Correct 74 ms 10504 KB Output is correct