제출 #125830

#제출 시각아이디문제언어결과실행 시간메모리
125830mechfrog88Valley (BOI19_valley)C++14
59 / 100
3031 ms25764 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #pragma GCC optimize("unroll-loops,no-stack-protector") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") using namespace __gnu_pbds; using namespace std; template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; typedef long long ll; typedef long double ld; struct node{ ll point; ll index; ll weight; }; struct ed{ ll u,v,w; }; vector <vector<node>> graph; vector <ll> euler; vector <pair<ll,ll>> pos; vector <ed> edge; vector <ll> index1; void dfs(ll p, ll v){ pos[v].first = euler.size(); index1[v] = euler.size(); euler.push_back(v); for (int z=0;z<graph[v].size();z++){ if (graph[v][z].point == p) continue; dfs(v,graph[v][z].point); euler.push_back(v); } pos[v].second = euler.size()-1; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); ll n,s,q,e; cin >> n >> s >> q >> e; graph.resize(n+1); for (int z=0;z<n-1;z++){ node temp; ll a,b; cin >> a >> b >> temp.weight; temp.index = z+1; temp.point = b; graph[a].push_back(temp); temp.point = a; graph[b].push_back(temp); ed ede; ede.u = a; ede.v = b; ede.w = temp.weight; edge.push_back(ede); } vector <bool> shops(n+1,false); for (int z=0;z<s;z++){ ll temp; cin >> temp; shops[temp] = true; } pos.resize(n+1); index1.resize(n+1); dfs(0,1); if (s == n){ for (int z=0;z<q;z++){ ll k,t; cin >> k >> t; k--; ll l,r; ll s1 = pos[edge[k].u].second-pos[edge[k].u].first; ll s2 = pos[edge[k].v].second-pos[edge[k].v].first; if (s1 > s2){ l = pos[edge[k].v].first; r = pos[edge[k].v].second; } else{ l = pos[edge[k].u].first; r = pos[edge[k].u].second; } bool in1 = false; bool in2 = false; if (l <= index1[t] && index1[t] <= r){ in1 = true; } if (l <= index1[e] && index1[e] <= r){ in2 = true; } if (in1 ^ in2){ cout << 0 << endl; } else { cout << "escaped" << endl; } } return 0; } for (int z=0;z<q;z++){ ll r,t; cin >> r >> t; vector <ll> distance(n+1,LLONG_MAX); queue <node> que; vector <bool> visited(n+1,false); visited[t] = true; distance[t] = 0; for (int x=0;x<graph[t].size();x++){ if (graph[t][x].index == r) continue; if (visited[graph[t][x].point]) continue; distance[graph[t][x].point] = graph[t][x].weight; que.push(graph[t][x]); } while (!que.empty()){ node temp = que.front(); ll v = temp.point; visited[v] = true; que.pop(); for (int x=0;x<graph[v].size();x++){ if (graph[v][x].index == r) continue; if (visited[graph[v][x].point]) continue; distance[graph[v][x].point] = distance[v]+graph[v][x].weight; que.push(graph[v][x]); } } if (visited[e] == true){ cout << "escaped" << endl; } else { ll mini = LLONG_MAX; for (int z=1;z<=n;z++){ if (shops[z]) mini = min(distance[z],mini); } if (mini == LLONG_MAX){ cout << "oo" << endl; } else { cout << mini << endl; } } } }

컴파일 시 표준 에러 (stderr) 메시지

valley.cpp: In function 'void dfs(ll, ll)':
valley.cpp:36:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int z=0;z<graph[v].size();z++){
               ~^~~~~~~~~~~~~~~~
valley.cpp: In function 'int main()':
valley.cpp:112:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int x=0;x<graph[t].size();x++){
                ~^~~~~~~~~~~~~~~~
valley.cpp:123:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int x=0;x<graph[v].size();x++){
                 ~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...