Submission #950771

#TimeUsernameProblemLanguageResultExecution timeMemory
950771IrateRoadside Advertisements (NOI17_roadsideadverts)C++17
47 / 100
1044 ms8812 KiB
#include<bits/stdc++.h> using namespace std; const int mxN = 5e4 + 5; vector<pair<int, int>> G[mxN]; vector<int>path, W; vector<bool>edge; int p[5]; void dfs(int node, int par){ bool check = 0; for(int i = 0;i < 5;++i){ check |= (node == p[i]); } if(check){ for(int &i : path){ edge[i] = 1; } } for(auto i : G[node]){ int to = i.first, indx = i.second; if(to != par){ path.push_back(indx); dfs(to, node); path.pop_back(); } } } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); int n; cin >> n; W.resize(n); for(int i = 1;i < n;++i){ int u, v, w; cin >> u >> v >> w; W[i - 1] = w; G[u].push_back({v, i - 1}); G[v].push_back({u, i - 1}); } edge.resize(n); int q; cin >> q; while(q--){ for(int i = 0;i < n;++i){ edge[i] = 0; } for(int i = 0;i < 5;++i){ cin >> p[i]; } dfs(p[0], p[0]); long long res = 0; for(int i = 0;i < n;++i){ if(edge[i])res += W[i]; } cout << res << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...