Submission #478006

#TimeUsernameProblemLanguageResultExecution timeMemory
478006sumit_kk10Roadside Advertisements (NOI17_roadsideadverts)C++17
7 / 100
145 ms12532 KiB
#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"; 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){
      |                                ~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...