Submission #478007

#	Time	Username	Problem	Language	Result	Execution time	Memory
478007		sumit_kk10	Roadside Advertisements (NOI17_roadsideadverts)	C++17	100 / 100	143 ms	14080 KiB

roadsideadverts

#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 (stderr)

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 / 7
• Subtask 2: 23 / 23
• Subtask 3: 40 / 40
• Subtask 4: 30 / 30