oj.uz

Submission #401005

# Submission time Handle Problem Language Result Execution time Memory
401005 2021-05-09T06:20:04 Z alireza_kaviani Valley (BOI19_valley) C++11
0 / 100
 125 ms 12968 KB 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
 
#define all(x)						(x).begin(),(x).end()
#define X							first
#define Y							second
#define sep							' '
#define endl						'\n'
#define SZ(x)						ll(x.size())
 
const ll MAXN = 1e5 + 10;
const ll LOG = 20;
const ll INF = 8e18;
const ll MOD = 1e9 + 7; //998244353; //1e9 + 9;
 
int n , s , q , e , timer , st[MAXN] , fn[MAXN] , shop[MAXN];
vector<pii> adj[MAXN] , E;
 
void PreDFS(int v , int p = -1){
	st[v] = timer++;
	for(pii i : adj[v]){
		int u = i.X , w = i.Y;
		if(u == p)	continue;
		PreDFS(u , v);
	}
	fn[v] = timer;
}
 
int isPar(int v , int u){
	return (st[v] <= st[u] && st[u] <= fn[v]);
}
 
int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
 
	cin >> n >> s >> q >> e;
	for(int i = 1 ; i < n ; i++){
		int v , u , w;
		cin >> v >> u >> w;
		adj[v].push_back({u , w});
		adj[u].push_back({v , w});
		E.push_back({u , v});
	}
	for(int i = 0 ; i < s ; i++){
		int v; cin >> v;
		shop[v] = 1;
	}
	PreDFS(1);
	for(int i = 0 ; i + 1 < n ; i++){
		if(st[E[i].X] > st[E[i].Y])	swap(E[i].X , E[i].Y);
	}
	while(q--){
		int u , v;
		cin >> u >> v; u--;
		u = E[u].Y;	//cout << u << endl;
		if(isPar(u , v) == isPar(u , e)){
			cout << "escaped" << endl;
			continue;
		}
		cout << 0 << endl;
	}
 
    return 0;
}
/*
 
*/

Compilation message

valley.cpp: In function 'void PreDFS(int, int)':
valley.cpp:26:17: warning: unused variable 'w' [-Wunused-variable]
   26 |   int u = i.X , w = i.Y;
      |                 ^

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 2764 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 2764 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 12968 KB Output is correct
2 Correct 125 ms 12684 KB Output is correct
3 Incorrect 116 ms 12596 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 2764 KB Output isn't correct
2 Halted 0 ms 0 KB -