Submission #860195

#TimeUsernameProblemLanguageResultExecution timeMemory
860195maks007Valley (BOI19_valley)C++14
0 / 100
323 ms41732 KiB
#include "bits/stdc++.h" using namespace std; #define int long long vector <vector <pair <int,int>>> g; set <int> shop; vector <pair <int,int>> edge; vector <int> deep; int root, escape, mn_shop, jmp[(int)1e5][32]; void count_depth(int v, int p = -1, int depth = 0) { deep[v] = depth; jmp[v][0]=p; for(auto [u, w] : g[v]) { if(u == p) continue; count_depth(u, v, depth+1); } } int get(int k, int n) { for(int i = 31; i >= 0; i --) { if(k - i >= 0) { n = jmp[n][i]; k -= (1 << i); } } return n; } void dfs(int v, const int &idx, int p = -1, int dist = 0) { if(v == root) { escape = 1; } if(shop.count(v)) mn_shop = min(mn_shop, dist); for(auto [u, w] : g[v]) { if(u == p) continue; if(u == edge[idx].first && v == edge[idx].second) continue; if(u == edge[idx].second && v == edge[idx].first) continue; dfs(u, idx, v, dist + w); } } signed main () { int n, shopsz, query; cin >> n >> shopsz >> query >> root; root --; g.resize(n); deep.resize(n); for(int i = 0; i < n - 1; i ++) { int u, v; cin >> u >> v; u --, v --; int w; cin >> w; g[v].push_back({u, w}); g[u].push_back({v, w}); edge.push_back({u, v}); } while(shopsz --) { int x; cin >> x; shop.insert(x-1); } count_depth(root); if(shop.size() == n) { for(int dist = 1; dist < 32; dist ++) { for(int i = 0; i < n; i ++) { if(jmp[i][dist-1] == -1) jmp[i][dist] = -1; else jmp[i][dist] = jmp[jmp[i][dist-1]][dist-1]; } } } while(query --) { int idx, v; cin >> idx >> v; idx --, v --; if(shop.size() == n) { if(deep[edge[idx].first] < deep[edge[idx].second]) swap(edge[idx].first, edge[idx].second); int which = edge[idx].first; if(deep[which] > deep[v]) { cout << "escaped\n"; continue; } int dist = deep[v] - deep[which]; if(get(dist, v) == which) cout << 0 << "\n"; else cout << "escaped\n"; continue; } escape = 0; mn_shop = LLONG_MAX; dfs(v, idx); if(escape) { cout << "escaped\n"; }else if(mn_shop != LLONG_MAX) { cout << mn_shop << "\n"; }else cout << "oo\n"; } return 0; }

Compilation message (stderr)

valley.cpp: In function 'void count_depth(long long int, long long int, long long int)':
valley.cpp:16:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   16 |  for(auto [u, w] : g[v]) {
      |           ^
valley.cpp: In function 'void dfs(long long int, const long long int&, long long int, long long int)':
valley.cpp:37:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   37 |  for(auto [u, w] : g[v]) {
      |           ^
valley.cpp: In function 'int main()':
valley.cpp:67:17: warning: comparison of integer expressions of different signedness: 'std::set<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   67 |  if(shop.size() == n) {
      |     ~~~~~~~~~~~~^~~~
valley.cpp:79:18: warning: comparison of integer expressions of different signedness: 'std::set<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   79 |   if(shop.size() == 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...