oj.uz

Submission #624109

# Submission time Handle Problem Language Result Execution time Memory
624109 2022-08-07T09:14:24 Z PoonYaPat Roadside Advertisements (NOI17_roadsideadverts) C++14
7 / 100
 19 ms 6684 KB 
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;

int n,q,p[20][50001],d[50001],level[50001];
vector<pii> adj[50001];

void dfs(int x, int par) {
    p[x][0]=par;
    level[x]=level[par]+1;
    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;
        d[s.first]=d[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 dis(int x, int y) {
    return d[x]+d[y]-2*d[lca(x,y)];
}

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

    int ans=dis(a[1],a[2]), top=lca(a[1],a[2]);

    for (int i=3; i<=5; ++i) {
        bool have=false;

        for (int j=1; j<i; ++j) {
            for (int k=j+1; k<i; ++k) {
                if (dis(a[j],a[k])==dis(a[j],a[i])+dis(a[i],a[k])) have=true;
            }
        }

        if (!have) {
            for (int j=1; j<i; ++j) {
                if (lca(a[i],a[j])==a[j]) {
                    ans+=dis(a[i],a[j]);
                    have=true;
                    break;
                }
            }
        }

        if (!have) {
            if (level[lca(a[i],a[1])]<level[top]) {
                ans+=dis(top,a[i]);
                top=lca(a[i],a[1]);
                have=true;
            }
        }

        if (!have) {
            int mindis=INT_MAX;
            for (int j=1; j<i; ++j) {
                mindis=min(mindis,dis(a[i],lca(a[i],a[j])));
            }
            ans+=mindis;
        }
    }
    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 a,b,w;
        cin>>a>>b>>w;
        adj[a].push_back(pii(b,w));
        adj[b].push_back(pii(a,w));
    }
    dfs(0,0);
    cin>>q;
    while (q--) solve();
}

Subtask #1
7.0 / 7.0

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

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 18 ms 6040 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 19 ms 6684 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Runtime error 18 ms 6040 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -