oj.uz

Submission #640348

# Submission time Handle Problem Language Result Execution time Memory
640348 2022-09-14T10:07:38 Z PoonYaPat Roadside Advertisements (NOI17_roadsideadverts) C++14
100 / 100
 78 ms 11028 KB 
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;

int n,m,a[6];
vector<pii> adj[50001];
int level[50001],p[50001][17],dis[50001];

void dfs(int x, int par) {
    level[x]=level[par]+1;
    p[x][0]=par;
    for (int i=1; i<=16; ++i) {
        p[x][i]=p[p[x][i-1]][i-1];
    }

    for (auto s : adj[x]) {
        if (s.first==par) continue;
        dis[s.first]=dis[x]+s.second;
        dfs(s.first,x);
    }
}

int lca(int x, int y) {
    if (level[x]<level[y]) swap(x,y);

    int dif=level[x]-level[y];
    for (int i=0; i<=16; ++i) {
        if (dif&(1<<i)) x=p[x][i];
    }
    if (x==y) return x;

    for (int i=16; i>=0; --i) {
        if (p[x][i]!=p[y][i]) {
            x=p[x][i];
            y=p[y][i];
        }
    }
    return p[x][0];
}

int dist(int x, int y) {
    return dis[x]+dis[y]-2*dis[lca(x,y)];
}

void solve() {
    for (int i=1; i<=5; ++i) cin>>a[i];
    int top_node, min_level=INT_MAX;

    for (int i=2; i<=5; ++i) {
        int node=lca(a[1],a[i]);
        if (level[node]<min_level) {
            min_level=level[node];
            top_node=node;
        }
    }

    vector<pii> v; //(level,node)
    for (int i=1; i<=5; ++i) v.push_back(pii(level[a[i]],a[i]));
    sort(v.begin(),v.end());

    int ans=0;
    for (int i=0; i<5; ++i) {
        int node=v[i].second;
        int mmin=dist(top_node,node);
        for (int j=0; j<i; ++j) mmin=min(mmin,dis[node]-dis[lca(node,v[j].second)]);
        ans+=mmin;
    }
    cout<<ans<<"\n";
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n;
    for (int i=0; i<n-1; ++i) {
        int x,y,w;
        cin>>x>>y>>w;
        adj[x].push_back(pii(y,w));
        adj[y].push_back(pii(x,w));
    }
    dfs(0,0);
    cin>>m;
    while (m--) solve();
}

Compilation message

roadsideadverts.cpp: In function 'void solve()':
roadsideadverts.cpp:42:35: warning: 'top_node' may be used uninitialized in this function [-Wmaybe-uninitialized]
   42 |     return dis[x]+dis[y]-2*dis[lca(x,y)];
      |                                ~~~^~~~~
roadsideadverts.cpp:47:9: note: 'top_node' was declared here
   47 |     int top_node, min_level=INT_MAX;
      |         ^~~~~~~~

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 58 ms 8472 KB Output is correct
2 Correct 59 ms 10960 KB Output is correct
3 Correct 53 ms 10928 KB Output is correct
4 Correct 68 ms 11012 KB Output is correct
5 Correct 70 ms 10916 KB Output is correct
6 Correct 54 ms 10924 KB Output is correct
7 Correct 54 ms 10916 KB Output is correct
8 Correct 53 ms 11028 KB Output is correct
9 Correct 55 ms 10988 KB Output is correct
10 Correct 59 ms 11000 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 7028 KB Output is correct
2 Correct 32 ms 10080 KB Output is correct
3 Correct 42 ms 10120 KB Output is correct
4 Correct 30 ms 10168 KB Output is correct
5 Correct 34 ms 10148 KB Output is correct
6 Correct 33 ms 10060 KB Output is correct
7 Correct 33 ms 10176 KB Output is correct
8 Correct 30 ms 10128 KB Output is correct
9 Correct 30 ms 10180 KB Output is correct
10 Correct 30 ms 10088 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 58 ms 8472 KB Output is correct
3 Correct 59 ms 10960 KB Output is correct
4 Correct 53 ms 10928 KB Output is correct
5 Correct 68 ms 11012 KB Output is correct
6 Correct 70 ms 10916 KB Output is correct
7 Correct 54 ms 10924 KB Output is correct
8 Correct 54 ms 10916 KB Output is correct
9 Correct 53 ms 11028 KB Output is correct
10 Correct 55 ms 10988 KB Output is correct
11 Correct 59 ms 11000 KB Output is correct
12 Correct 24 ms 7028 KB Output is correct
13 Correct 32 ms 10080 KB Output is correct
14 Correct 42 ms 10120 KB Output is correct
15 Correct 30 ms 10168 KB Output is correct
16 Correct 34 ms 10148 KB Output is correct
17 Correct 33 ms 10060 KB Output is correct
18 Correct 33 ms 10176 KB Output is correct
19 Correct 30 ms 10128 KB Output is correct
20 Correct 30 ms 10180 KB Output is correct
21 Correct 30 ms 10088 KB Output is correct
22 Correct 59 ms 9512 KB Output is correct
23 Correct 43 ms 8156 KB Output is correct
24 Correct 54 ms 10512 KB Output is correct
25 Correct 58 ms 10480 KB Output is correct
26 Correct 57 ms 10520 KB Output is correct
27 Correct 67 ms 10636 KB Output is correct
28 Correct 78 ms 10468 KB Output is correct
29 Correct 55 ms 10524 KB Output is correct
30 Correct 54 ms 10464 KB Output is correct
31 Correct 64 ms 10456 KB Output is correct