oj.uz

Submission #478005

# Submission time Handle Problem Language Result Execution time Memory
478005 2021-10-05T03:29:47 Z sumit_kk10 Roadside Advertisements (NOI17_roadsideadverts) C++17
100 / 100
 152 ms 15116 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 8144 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 13560 KB Output is correct
2 Correct 118 ms 15036 KB Output is correct
3 Correct 128 ms 15048 KB Output is correct
4 Correct 105 ms 15072 KB Output is correct
5 Correct 112 ms 15020 KB Output is correct
6 Correct 106 ms 15012 KB Output is correct
7 Correct 116 ms 15084 KB Output is correct
8 Correct 118 ms 15112 KB Output is correct
9 Correct 114 ms 15116 KB Output is correct
10 Correct 125 ms 15044 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 11816 KB Output is correct
2 Correct 36 ms 14288 KB Output is correct
3 Correct 43 ms 14260 KB Output is correct
4 Correct 38 ms 14508 KB Output is correct
5 Correct 37 ms 14244 KB Output is correct
6 Correct 38 ms 14280 KB Output is correct
7 Correct 38 ms 14284 KB Output is correct
8 Correct 39 ms 14288 KB Output is correct
9 Correct 43 ms 14216 KB Output is correct
10 Correct 41 ms 14200 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8144 KB Output is correct
2 Correct 140 ms 13560 KB Output is correct
3 Correct 118 ms 15036 KB Output is correct
4 Correct 128 ms 15048 KB Output is correct
5 Correct 105 ms 15072 KB Output is correct
6 Correct 112 ms 15020 KB Output is correct
7 Correct 106 ms 15012 KB Output is correct
8 Correct 116 ms 15084 KB Output is correct
9 Correct 118 ms 15112 KB Output is correct
10 Correct 114 ms 15116 KB Output is correct
11 Correct 125 ms 15044 KB Output is correct
12 Correct 31 ms 11816 KB Output is correct
13 Correct 36 ms 14288 KB Output is correct
14 Correct 43 ms 14260 KB Output is correct
15 Correct 38 ms 14508 KB Output is correct
16 Correct 37 ms 14244 KB Output is correct
17 Correct 38 ms 14280 KB Output is correct
18 Correct 38 ms 14284 KB Output is correct
19 Correct 39 ms 14288 KB Output is correct
20 Correct 43 ms 14216 KB Output is correct
21 Correct 41 ms 14200 KB Output is correct
22 Correct 152 ms 13644 KB Output is correct
23 Correct 110 ms 12240 KB Output is correct
24 Correct 128 ms 14544 KB Output is correct
25 Correct 127 ms 14644 KB Output is correct
26 Correct 138 ms 14552 KB Output is correct
27 Correct 132 ms 14540 KB Output is correct
28 Correct 137 ms 14636 KB Output is correct
29 Correct 126 ms 14672 KB Output is correct
30 Correct 129 ms 14664 KB Output is correct
31 Correct 128 ms 14652 KB Output is correct