# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
125830 |
2019-07-06T12:18:55 Z |
mechfrog88 |
Valley (BOI19_valley) |
C++14 |
|
3000 ms |
25764 KB |
#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;
}
}
}
}
Compilation message
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 time |
Memory |
Grader output |
1 |
Correct |
49 ms |
504 KB |
Output is correct |
2 |
Correct |
52 ms |
632 KB |
Output is correct |
3 |
Correct |
50 ms |
504 KB |
Output is correct |
4 |
Correct |
30 ms |
504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
49 ms |
504 KB |
Output is correct |
2 |
Correct |
52 ms |
632 KB |
Output is correct |
3 |
Correct |
50 ms |
504 KB |
Output is correct |
4 |
Correct |
30 ms |
504 KB |
Output is correct |
5 |
Correct |
21 ms |
504 KB |
Output is correct |
6 |
Correct |
26 ms |
504 KB |
Output is correct |
7 |
Correct |
33 ms |
592 KB |
Output is correct |
8 |
Correct |
20 ms |
632 KB |
Output is correct |
9 |
Correct |
27 ms |
504 KB |
Output is correct |
10 |
Correct |
34 ms |
632 KB |
Output is correct |
11 |
Correct |
6 ms |
504 KB |
Output is correct |
12 |
Correct |
6 ms |
504 KB |
Output is correct |
13 |
Correct |
5 ms |
632 KB |
Output is correct |
14 |
Correct |
37 ms |
504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
417 ms |
21952 KB |
Output is correct |
2 |
Correct |
429 ms |
21896 KB |
Output is correct |
3 |
Correct |
455 ms |
22372 KB |
Output is correct |
4 |
Correct |
434 ms |
23336 KB |
Output is correct |
5 |
Correct |
426 ms |
23464 KB |
Output is correct |
6 |
Correct |
442 ms |
25764 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
49 ms |
504 KB |
Output is correct |
2 |
Correct |
52 ms |
632 KB |
Output is correct |
3 |
Correct |
50 ms |
504 KB |
Output is correct |
4 |
Correct |
30 ms |
504 KB |
Output is correct |
5 |
Correct |
21 ms |
504 KB |
Output is correct |
6 |
Correct |
26 ms |
504 KB |
Output is correct |
7 |
Correct |
33 ms |
592 KB |
Output is correct |
8 |
Correct |
20 ms |
632 KB |
Output is correct |
9 |
Correct |
27 ms |
504 KB |
Output is correct |
10 |
Correct |
34 ms |
632 KB |
Output is correct |
11 |
Correct |
6 ms |
504 KB |
Output is correct |
12 |
Correct |
6 ms |
504 KB |
Output is correct |
13 |
Correct |
5 ms |
632 KB |
Output is correct |
14 |
Correct |
37 ms |
504 KB |
Output is correct |
15 |
Correct |
417 ms |
21952 KB |
Output is correct |
16 |
Correct |
429 ms |
21896 KB |
Output is correct |
17 |
Correct |
455 ms |
22372 KB |
Output is correct |
18 |
Correct |
434 ms |
23336 KB |
Output is correct |
19 |
Correct |
426 ms |
23464 KB |
Output is correct |
20 |
Correct |
442 ms |
25764 KB |
Output is correct |
21 |
Execution timed out |
3031 ms |
19968 KB |
Time limit exceeded |
22 |
Halted |
0 ms |
0 KB |
- |