This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// absolutely incredible
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
#define REP(i, a, b) for(int i = a; i >= b; --i)
#define left _________left
#define right _________right
#define NAME ""
const int mod = 1e9 + 7;
bool maximize(int &u, int v){
if(v > u){
u = v;
return true;
}
return false;
}
bool minimize(int &u, int v){
if(v < u){
u = v;
return true;
}
return false;
}
bool maximizell(long long &u, long long v){
if(v > u){
u = v;
return true;
}
return false;
}
bool minimizell(long long &u, long long v){
if(v < u){
u = v;
return true;
}
return false;
}
int fastPow(int a, int n){
if(n == 0) return 1;
int t = fastPow(a, n >> 1);
t = 1ll * t * t % mod;
if(n & 1) t = 1ll * t * a % mod;
return t;
}
void add(int &u, int v){
u += v;
if(u >= mod) u -= mod;
}
void sub(int &u, int v){
u -= v;
if(u < 0) u += mod;
}
const int maxN = 1e5 + 5;
int n, q, s, e;
tuple<int, int, int> edge[maxN];
vector<int> adj[maxN];
int spe[maxN];
const long long INFLL = 1e18;
namespace subtask12{
bool check(){
return (n <= 100 && q <= 10000) || (n <= 1000 && q <= 1000);
}
long long dist[1001][1001];
void bfs(int st){
memset(dist[st], -1, sizeof(dist[st]));
dist[st][st] = 0;
queue<int> q;
q.push(st);
while(!q.empty()){
int p = q.front();
q.pop();
for(int id : adj[p]){
auto[u, v, w] = edge[id];
if(v == p) v = u;
if(dist[st][v] == -1){
dist[st][v] = dist[st][p] + w;
q.push(v);
}
}
}
}
int in[1001], out[1001], timeDFS;
void dfs(int u = 1){
in[u] = ++timeDFS;
for(int id : adj[u]){
auto[p, v, w] = edge[id];
if(v == u) v = p;
if(in[v] == 0){
dfs(v);
}
}
out[u] = timeDFS;
}
bool inside(int u, int v){
return in[u] <= in[v] && out[u] >= out[v];
}
void solve(){
FOR(i, 1, n)bfs(i);
dfs();
while(q--){
int id, c;
cin >> id >> c;
auto[u, v, w] = edge[id];
long long res = INFLL;
if(in[u] > in[v])swap(u, v);
if(!inside(v, c)){
if(!inside(v, e)){
cout << "escaped\n";
continue;
}
FOR(i, 1, s){
if(!inside(v, spe[i]))res = min(res, dist[spe[i]][c]);
}
if(res == INFLL)cout << "oo\n";
else cout << res << '\n';
continue;
}
if(inside(v, e)){
cout << "escaped\n";
continue;
}
FOR(i, 1, s){
if(inside(v, spe[i]))res = min(res, dist[spe[i]][c]);
}
if(res == INFLL){
cout << "oo\n";
}else cout << res << "\n";
}
}
}
namespace subtask3{
bool check(){
return s == n;
}
int in[maxN], out[maxN], timeDFS;
void dfs(int u = 1){
in[u] = ++timeDFS;
for(int id : adj[u]){
auto[p, v, w] = edge[id];
if(v == u) v = p;
if(in[v] == 0){
dfs(v);
}
}
out[u] = timeDFS;
}
bool inside(int u, int v){
return in[u] <= in[v] && out[u] >= out[v];
}
void solve(){
dfs();
while(q--){
int id, c;
cin >> id >> c;
auto[u, v, w] = edge[id];
if(in[u] > in[v])swap(u, v);
bool ok1 = inside(v, c);
bool ok2 = inside(v, e);
if(ok1 == ok2){
cout << "escaped\n";
}else cout << "0\n";
}
}
}
void solve(){
cin >> n >> s >> q >> e;
FOR(i, 1, n - 1){
int u, v, w;
cin >> u >> v >> w;
edge[i] = {u, v, w};
adj[u].push_back(i);
adj[v].push_back(i);
}
FOR(i, 1, s)cin >> spe[i];
if(subtask12 :: check()) return subtask12 :: solve();
if(subtask3 :: check()) return subtask3 :: solve();
}
int main(){
if(fopen(NAME".inp", "r")){
freopen(NAME".inp", "r", stdin);
freopen(NAME".out", "w", stdout);
}
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t = 1;
// cin >> t;
while(t--){
solve();
}
return 0;
}
Compilation message (stderr)
valley.cpp: In function 'int main()':
valley.cpp:180:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
180 | freopen(NAME".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:181:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
181 | freopen(NAME".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |