| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 552119 |
2022-04-22T12:59:12 Z |
errorgorn |
Jail (JOI22_jail) |
C++17 |
|
10 ms |
3156 KB |
// Super Idol的笑容
// 都没你的甜
// 八月正午的阳光
// 都没你耀眼
// 热爱105°C的你
// 滴滴清纯的蒸馏水
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define int long long
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << ": " << x << endl
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
int n,q;
vector<int> al[120005];
ii arr[120005];
int d[120005];
int tkd[120005][19];
void dfs(int i,int p){
for (auto it:al[i]){
if (it==p) continue;
d[it]=d[i]+1;
int curr=tkd[it][0]=i;
rep(x,0,19){
if (curr==-1) continue;
curr=tkd[it][x+1]=tkd[curr][x];
}
dfs(it,i);
}
}
int mov(int i,int k){
rep(x,0,19) if (k&(1<<x)) i=tkd[i][x];
return i;
}
int lca(int i,int j){
if (d[i]<d[j]) swap(i,j);
i=mov(i,d[i]-d[j]);
if (i==j) return i;
rep(x,19,0) if (tkd[i][x]!=tkd[j][x]){
i=tkd[i][x];
j=tkd[j][x];
}
return tkd[i][0];
}
int dist(int i,int j){
int g=lca(i,j);
return d[i]+d[j]-2*d[g];
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin.exceptions(ios::badbit | ios::failbit);
int TC;
cin>>TC;
while (TC--){
cin>>n;
rep(x,1,n+1) al[x].clear();
int a,b;
rep(x,1,n){
cin>>a>>b;
al[a].pub(b);
al[b].pub(a);
}
rep(x,1,n+1) rep(y,0,19) tkd[x][y]=-1;
dfs(1,-1);
cin>>q;
rep(x,0,q){
cin>>a>>b;
arr[x]={a,b};
}
bool ok=true;
rep(x,0,q) rep(y,0,q) if (x!=y){
if (dist(arr[x].fi,arr[y].fi)+dist(arr[y].fi,arr[x].se)==dist(arr[x].fi,arr[x].se) &&
dist(arr[x].fi,arr[y].se)+dist(arr[y].se,arr[x].se)==dist(arr[x].fi,arr[x].se)){
ok=false;
}
if (dist(arr[x].fi,arr[y].se)+dist(arr[y].se,arr[x].se)==dist(arr[x].fi,arr[x].se) &&
dist(arr[y].fi,arr[x].se)+dist(arr[x].se,arr[y].se)==dist(arr[y].fi,arr[y].se)){
ok=false;
}
}
if (ok) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3156 KB |
Output is correct |
| 2 |
Correct |
3 ms |
3156 KB |
Output is correct |
| 3 |
Correct |
2 ms |
3156 KB |
Output is correct |
| 4 |
Incorrect |
10 ms |
3156 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3156 KB |
Output is correct |
| 2 |
Correct |
2 ms |
3156 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
3156 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3156 KB |
Output is correct |
| 2 |
Correct |
2 ms |
3156 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
3156 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3156 KB |
Output is correct |
| 2 |
Correct |
2 ms |
3156 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
3156 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3156 KB |
Output is correct |
| 2 |
Correct |
2 ms |
3156 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
3156 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3156 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
3156 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3156 KB |
Output is correct |
| 2 |
Correct |
3 ms |
3156 KB |
Output is correct |
| 3 |
Correct |
2 ms |
3156 KB |
Output is correct |
| 4 |
Incorrect |
10 ms |
3156 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
