oj.uz

Submission #731817

# Submission time Handle Problem Language Result Execution time Memory
731817 2023-04-28T03:34:08 Z Trunkty Roadside Advertisements (NOI17_roadsideadverts) C++14
100 / 100
 253 ms 32964 KB 
#include <bits/extc++.h>
using namespace std;
typedef long long ll;
#define int ll

int n,q;
vector<vector<int>> roads[50005];
int jump[50005][21],dist[50005][21],dep[50005];
int curr=0;

void dfs(int x, int p){
    for(vector<int> i:roads[x]){
        if(i[0]!=p){
            jump[i[0]][0] = x;
            dist[i[0]][0] = i[1];
            dep[i[0]] = dep[x]+1;
            dfs(i[0],x);
        }
    }
}

int lca(int a, int b){
    curr = 0;
    if(dep[a]>dep[b]){
        swap(a,b);
    }
    for(int j=20;j>=0;j--){
        if(dep[b]-(1<<j)>=dep[a]){
            curr += dist[b][j];
            b = jump[b][j];
        }
    }
    if(a==b){
        return a;
    }
    for(int j=20;j>=0;j--){
        if(jump[a][j]!=jump[b][j]){
            curr += dist[a][j];
            curr += dist[b][j];
            a = jump[a][j];
            b = jump[b][j];
        }
    }
    curr += dist[a][0]+dist[b][0];
    return jump[a][0];
}

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
    cin >> n;
    for(int i=1;i<=n-1;i++){
        int a,b,c;
        cin >> a >> b >> c;
        roads[a].push_back({b,c});
        roads[b].push_back({a,c});
    }
    dfs(0,-1);
    for(int j=1;j<=20;j++){
        for(int i=1;i<=n;i++){
            jump[i][j] = jump[jump[i][j-1]][j-1];
            dist[i][j] = dist[i][j-1]+dist[jump[i][j-1]][j-1];
        }
    }
    cin >> q;
    for(int i=1;i<=q;i++){
        int a,b,c,d,e,ans=0;
        cin >> a >> b >> c >> d >> e;
        set<int> s = {a,b,c,d,e};
        while(s.size()>1){
            vector<vector<int>> v;
            for(int j:s){
                for(int k:s){
                    if(j==k){
                        continue;
                    }
                    int p = lca(j,k);
                    v.push_back({dep[p],curr,p,j,k});
                }
            }
            sort(v.begin(),v.end(),greater<vector<int>>());
            s.erase(v[0][3]);
            s.erase(v[0][4]);
            ans += v[0][1];
            s.insert(v[0][2]);
        }
        cout << ans << "\n";
    }
	return 0;
}

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 241 ms 28336 KB Output is correct
2 Correct 250 ms 32632 KB Output is correct
3 Correct 251 ms 32964 KB Output is correct
4 Correct 225 ms 32692 KB Output is correct
5 Correct 210 ms 32668 KB Output is correct
6 Correct 230 ms 32752 KB Output is correct
7 Correct 246 ms 32784 KB Output is correct
8 Correct 217 ms 32664 KB Output is correct
9 Correct 220 ms 32736 KB Output is correct
10 Correct 217 ms 32804 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 24608 KB Output is correct
2 Correct 77 ms 31064 KB Output is correct
3 Correct 84 ms 31156 KB Output is correct
4 Correct 88 ms 31056 KB Output is correct
5 Correct 86 ms 31028 KB Output is correct
6 Correct 79 ms 31072 KB Output is correct
7 Correct 78 ms 31068 KB Output is correct
8 Correct 88 ms 31036 KB Output is correct
9 Correct 82 ms 31064 KB Output is correct
10 Correct 76 ms 30988 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 241 ms 28336 KB Output is correct
3 Correct 250 ms 32632 KB Output is correct
4 Correct 251 ms 32964 KB Output is correct
5 Correct 225 ms 32692 KB Output is correct
6 Correct 210 ms 32668 KB Output is correct
7 Correct 230 ms 32752 KB Output is correct
8 Correct 246 ms 32784 KB Output is correct
9 Correct 217 ms 32664 KB Output is correct
10 Correct 220 ms 32736 KB Output is correct
11 Correct 217 ms 32804 KB Output is correct
12 Correct 74 ms 24608 KB Output is correct
13 Correct 77 ms 31064 KB Output is correct
14 Correct 84 ms 31156 KB Output is correct
15 Correct 88 ms 31056 KB Output is correct
16 Correct 86 ms 31028 KB Output is correct
17 Correct 79 ms 31072 KB Output is correct
18 Correct 78 ms 31068 KB Output is correct
19 Correct 88 ms 31036 KB Output is correct
20 Correct 82 ms 31064 KB Output is correct
21 Correct 76 ms 30988 KB Output is correct
22 Correct 253 ms 29548 KB Output is correct
23 Correct 156 ms 25768 KB Output is correct
24 Correct 222 ms 31444 KB Output is correct
25 Correct 240 ms 31428 KB Output is correct
26 Correct 206 ms 31436 KB Output is correct
27 Correct 214 ms 31332 KB Output is correct
28 Correct 239 ms 31440 KB Output is correct
29 Correct 232 ms 31332 KB Output is correct
30 Correct 221 ms 31424 KB Output is correct
31 Correct 243 ms 31504 KB Output is correct