| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 890861 |
2023-12-22T04:26:06 Z |
vjudge1 |
Jail (JOI22_jail) |
C++17 |
|
3 ms |
20640 KB |
#include <bits/stdc++.h>
using namespace std;/*
<<<<It's never too late for a new beginning in your life>>>>
Today is hard
tomorrow will worse
but the day after tomorrow will be the sunshine..
HARD WORK BEATS TALENT WHEN TALENT DOESN'T WORK HARD............
Never give up */
//The most CHALISHKANCHIK
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define int long long
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pair<int,int> > vii;
const long long N = 1e5+50, inf = 1e18, mod = 1e9+7;
vi g[N];
int pre[N];
int timer;
int tin[N], tout[N];
int up[20][N];
void dfs(int v, int pr) {
//~ cout << pr << ' ' << v << '\n';
pre[v] = pr;
tin[v] = ++timer;
up[0][v] = pr;
for (int i = 1; i <= 18; i++) {
up[i][v] = up[i - 1][ up[i - 1][v] ];
}
for (int to : g[v]) {
if (to == pr) continue;
dfs(to, v);
}
tout[v] = timer;
}
bool upper(int a, int b) {
return tin[a] <= tin[b] && tout[a] >= tout[b];
}
int lca(int a, int b) {
if (upper(a, b)) return a;
if (upper(b, a)) return b;
for (int i = 18; i >= 0; i--) {
if (!upper(up[i][a], b)) {
a = up[i][a];
}
}
return up[0][a];
}
vi path(int s, int t){
int h = lca(s, t);
vi ans;
while(s!=h){
ans.pb(s);
s = pre[s];
}
ans.pb(h);
vi res;
while(t!=h){
res.pb(t);
t = pre[t];
}
reverse(all(res));
for(auto i:res)ans.pb(i);
return ans;
}
void solve(){
int n;
cin >> n;
for(int i = 1; i <= n; i++)g[i].clear();
for(int i = 0; i < n-1; i++){
int a, b;
cin >> a >> b;
g[a].pb(b);
g[b].pb(a);
}
dfs(1, -1);
int m;
cin >> m;
vii ps(m);
for(int i = 0; i < m; i++){
cin >> ps[i].ff >> ps[i].ss;
}
sort(all(ps));
int pi, pj;
for(int i = 0; i < m-1; i++){
vi pathi = path(ps[i].ff, ps[i].ss);
pi = pathi.size();
for(int j = i+1; j < m; j++){
vi pathj = path(ps[j].ff, ps[j].ss);
pj = pathj.size();
for(int k = 0; k < min(pi, pj); k++){
if(pathi[k] == pathj[k]){
cout << "No\n";
return;
}
}
}
}
cout << "Yes\n";
}
main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int t = 1;
cin >> t;
while(t--){
solve();
}
}
Compilation message
jail.cpp:107:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
107 | main(){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
20572 KB |
Output is correct |
| 2 |
Correct |
3 ms |
20572 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
20572 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
20572 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
20572 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
20572 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
20572 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
20572 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
20572 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
20572 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
20572 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
20568 KB |
Output is correct |
| 2 |
Correct |
3 ms |
20568 KB |
Output is correct |
| 3 |
Correct |
3 ms |
20640 KB |
Output is correct |
| 4 |
Incorrect |
3 ms |
20572 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
20572 KB |
Output is correct |
| 2 |
Correct |
3 ms |
20572 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
20572 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
