oj.uz

Submission #478007

# Submission time Handle Problem Language Result Execution time Memory
478007 2021-10-05T03:36:38 Z sumit_kk10 Roadside Advertisements (NOI17_roadsideadverts) C++17
100 / 100
 143 ms 14080 KB 
#include<bits/stdc++.h>
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;
const int MOD = 1e9 + 7;
const int N = 50003 + 2;
vector<pair<int, int> > graph[N];
vector<pair<long long int, pair<int, int> > > edges;
long long dis[N], lvl[N], dp[N][(int) log2(N) + 2], component[N];
 
void dfs(int source, int par, int level, long long int cost){
    dp[source][0] = par;
    lvl[source] = level;
    dis[source] = cost;
    for(auto k : graph[source])
        if(k.first != par)
            dfs(k.first, source, level + 1, cost + k.second);
}
 
void init(int n){
    dfs(0, -1, 1, 0);
    for(int i = 1; i <= log2(n); ++i)
        for(int j = 0; j < n; ++j)
            if(dp[j][i - 1] != -1)
                dp[j][i] = dp[dp[j][i - 1]][i - 1];
}
 
int LCA(int u, int v, int n){
    if(lvl[u] > lvl[v])
        swap(u, v);
    int d = lvl[v] - lvl[u];
    while(d){
        int jump = log2(d);
        v = dp[v][jump];
        d -= (1LL << jump);
    }
    if(v == u)
        return v;
    for(int i = log2(n); i >= 0; --i){
        if(dp[v][i] != -1 and dp[v][i] != dp[u][i]){
            v = dp[v][i];
            u = dp[u][i];
        }
    }
    return dp[v][0];
}
 
int find(int a){
    while(1){
        if(a == component[a])
            return a;
        component[a] = component[component[a]];
        a = component[a];
    }
}
 
void merge(int a, int b){
    int u = find(a), v = find(b);
    component[u] = v;
}
 
long long MST(){
    long long ans = 0;
    for(int i = 0; i < edges.size(); ++i){
        int u = edges[i].second.first, v = edges[i].second.second, c = edges[i].first;
        if(find(u) == find(v))
            continue;
        ans += c;
        merge(u, v);
    }
    return ans;
}
 
void solve() {
    int n;
    cin >> n;
    for(int i = 1; i <= n - 1; ++i){
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].push_back({v, w});
        graph[v].push_back({u, w});
    }
    for(int i = 1; i <= n; ++i)
        component[i] = i;
    memset(dp, -1, sizeof dp);
    init(n);
    int q;
    cin >> q;
    while(q--){
        int a[5];
        for(int i = 0; i < 5; ++i)
            cin >> a[i];
        set<int> s;
        for(int i = 0; i < 5; ++i){
            for(int j = i + 1; j < 5; ++j){
                int p = LCA(a[i], a[j], n);
                s.insert(p);
            }
            s.insert(a[i]);
        }
        vector<int> nodes;
        for(auto k : s)
            nodes.push_back(k);
        for(int i = 0; i < nodes.size(); ++i){
            for(int j = i + 1; j < nodes.size(); ++j){
                int p = LCA(nodes[i], nodes[j], n);
                long long int cost = dis[nodes[i]] + dis[nodes[j]] - 2 * dis[p];
                edges.push_back({cost, {nodes[i], nodes[j]}});
            }
        }
        sort(edges.begin(), edges.end());
        cout << MST() << "\n";
        for(auto k : edges){
            component[k.second.first] = k.second.first;
            component[k.second.second] = k.second.second;
        }
        edges.clear();
    }
}
 
int main() {
    fast;
    int t = 1;
    // cin >> t;
    while(t--)
        solve();
    return 0;
}

Compilation message

roadsideadverts.cpp: In function 'long long int MST()':
roadsideadverts.cpp:63:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for(int i = 0; i < edges.size(); ++i){
      |                    ~~^~~~~~~~~~~~~~
roadsideadverts.cpp: In function 'void solve()':
roadsideadverts.cpp:103:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |         for(int i = 0; i < nodes.size(); ++i){
      |                        ~~^~~~~~~~~~~~~~
roadsideadverts.cpp:104:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |             for(int j = i + 1; j < nodes.size(); ++j){
      |                                ~~^~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 12524 KB Output is correct
2 Correct 117 ms 14056 KB Output is correct
3 Correct 116 ms 14016 KB Output is correct
4 Correct 122 ms 14072 KB Output is correct
5 Correct 111 ms 14080 KB Output is correct
6 Correct 114 ms 14020 KB Output is correct
7 Correct 108 ms 13980 KB Output is correct
8 Correct 110 ms 14032 KB Output is correct
9 Correct 126 ms 14020 KB Output is correct
10 Correct 120 ms 14008 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 11084 KB Output is correct
2 Correct 41 ms 13448 KB Output is correct
3 Correct 36 ms 13524 KB Output is correct
4 Correct 39 ms 13488 KB Output is correct
5 Correct 37 ms 13472 KB Output is correct
6 Correct 36 ms 13468 KB Output is correct
7 Correct 41 ms 13508 KB Output is correct
8 Correct 38 ms 13436 KB Output is correct
9 Correct 34 ms 13520 KB Output is correct
10 Correct 40 ms 13428 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8140 KB Output is correct
2 Correct 143 ms 12524 KB Output is correct
3 Correct 117 ms 14056 KB Output is correct
4 Correct 116 ms 14016 KB Output is correct
5 Correct 122 ms 14072 KB Output is correct
6 Correct 111 ms 14080 KB Output is correct
7 Correct 114 ms 14020 KB Output is correct
8 Correct 108 ms 13980 KB Output is correct
9 Correct 110 ms 14032 KB Output is correct
10 Correct 126 ms 14020 KB Output is correct
11 Correct 120 ms 14008 KB Output is correct
12 Correct 34 ms 11084 KB Output is correct
13 Correct 41 ms 13448 KB Output is correct
14 Correct 36 ms 13524 KB Output is correct
15 Correct 39 ms 13488 KB Output is correct
16 Correct 37 ms 13472 KB Output is correct
17 Correct 36 ms 13468 KB Output is correct
18 Correct 41 ms 13508 KB Output is correct
19 Correct 38 ms 13436 KB Output is correct
20 Correct 34 ms 13520 KB Output is correct
21 Correct 40 ms 13428 KB Output is correct
22 Correct 141 ms 12560 KB Output is correct
23 Correct 118 ms 11212 KB Output is correct
24 Correct 141 ms 13768 KB Output is correct
25 Correct 124 ms 13524 KB Output is correct
26 Correct 122 ms 13572 KB Output is correct
27 Correct 130 ms 13536 KB Output is correct
28 Correct 128 ms 13504 KB Output is correct
29 Correct 125 ms 13508 KB Output is correct
30 Correct 123 ms 13548 KB Output is correct
31 Correct 134 ms 13508 KB Output is correct