Submission #587461

#TimeUsernameProblemLanguageResultExecution timeMemory
587461gg123_peRoadside Advertisements (NOI17_roadsideadverts)C++14
7 / 100
83 ms9676 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define f(i,a,b) for(ll i = a; i < b; i++) #define fa(i,a,b) for(ll i = a; i >= b; i--) const int N = 50005; const ll inf = 2e18; int n, a[6], d[N], tin[N], tout[N], c, p[N][16]; vector <pair<int,int>> adj[N]; vector <int> aux; void dfs(int u, int f){ p[u][0] = f; f(i,1,16) p[u][i] = p[p[u][i-1]][i-1]; tin[u] = c++; for(auto p: adj[u]){ int v = p.first, w = p.second; if(v == f) continue; d[v] = d[u] + w; dfs(v, u); } tout[u] = c++; } bool is(int u, int v){ return tin[u] <= tin[u] and tout[u] >= tout[v]; } int lca(int u, int v){ if(is(u, v)) return u; if(is(v, u)) return v; fa(i,15,0){ if(p[u][i] == 0 or is(p[u][i], v)) continue; u = p[u][i]; } return p[u][0]; } int main(){ cin >> n; f(i,1,n){ int u, v, w; cin >> u >> v >> w; adj[u].push_back({v, w}); adj[v].push_back({u, w}); } dfs(0, -1); int qe; cin >> qe; while(qe--){ bool fe = 0; vector <pair<int,int>> v; set <int> s; f(i,1,6){ cin >> a[i]; if(a[i] == 0) fe = 1; v.push_back({tin[a[i]], a[i]}); s.insert(a[i]); } if(!fe){ v.push_back({tin[0], 0}); s.insert(0); } sort(v.begin(), v.end()); int ans = 0, l = v.size(); f(i,1,l){ s.insert(lca(v[i].second, v[i-1].second)); } v.clear(); for(int x: s) v.push_back({tin[x], x}); sort(v.begin(), v.end()); stack <int> q; q.push(0); f(i,1,l){ int vi = v[i].second; while(1){ int x = q.top(); if(is(x, vi)){ ans += d[vi] - d[x]; if(x == 0){ aux.push_back(vi); } q.push(vi); break; } q.pop(); } } if(aux.size() == 1 and !fe){ ans -= d[aux[0]]; } cout << ans << "\n"; } return 0; }

Compilation message (stderr)

roadsideadverts.cpp: In function 'bool is(int, int)':
roadsideadverts.cpp:32:19: warning: self-comparison always evaluates to true [-Wtautological-compare]
   32 |     return tin[u] <= tin[u] and tout[u] >= tout[v];
      |            ~~~~~~ ^~ ~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...