| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 890935 |
2023-12-22T05:22:03 Z |
vjudge1 |
Jail (JOI22_jail) |
C++17 |
|
0 ms |
348 KB |
#include <bits/stdc++.h>
#define int long long
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define pb push_back
using namespace std;
const int N=1000;
vector <int> g[N];
int d[N],p[N];
int jmp[20][N];
void dfs(int v,int par){
p[v]=par;
for(auto to : g[v]){
if(to!=par){
d[to]=d[v]+1;
dfs(to,v);
}
}
}
int lca(int a,int b){
if(d[a]<d[b]){
swap(a,b);
}
int curv=a,curu=b;
for(int j=19;j>=0;j--){
if(d[jmp[curv][j]]>=d[curu]){
curv=jmp[curv][j];
}
}
if(curv==curu){
return curv;
}
for(int j=19;j>=0;j--){
if(jmp[curv][j]!=jmp[curu][j]){
curv=jmp[curv][j];
curu=jmp[curu][j];
}
}
return p[curv];
}
signed main(){
ios_base::sync_with_stdio();
cin.tie(0);
int t;cin>>t;
while(t--){
int n;cin>>n;
for(int i=0;i<n-1;i++){
int u,v;cin>>u>>v;
g[u].pb(v);
g[v].pb(u);
}
dfs(1,0);
p[1]=1;
for(int i=1;i<=n;i++){
jmp[i][0]=p[i];
}
for(int j=1;j<20;j++){
for(int i=1;i<=n;i++){
jmp[i][j]=jmp[jmp[i][j-1]][j-1];
}
}
int m;cin>>m;
vector <int> s(m),t(m);
vector <vector <int> > path(m);
for(int i=0;i<m;i++)cin>>s[i]>>t[i];
for(int i=0;i<m;i++){
int x=lca(s[i],t[i]);
int curv=s[i];
path[i].pb(curv);
while(curv!=x){
curv=p[curv];
path[i].pb(curv);
}
path[i].pop_back();
vector <int> v;
curv=t[i];
v.pb(curv);
while(curv!=x){
curv=p[curv];
v.pb(curv);
}
reverse(all(v));
for(auto x : v)path[i].pb(x);
}
bool flag=true;
for(int i=0;i<n;i++){
set <int> st;
int cnt=0;
for(int j=0;j<m;j++){
if(path[j].size()>=i+1){
cnt++;
st.insert(path[j][i]);
}
}
if(st.size()!=cnt){
flag=false;break;
}
}
if(flag)cout<<"Yes\n";
else cout<<"No\n";
for(int i=1;i<=n;i++){
g[i].clear();
d[i]=0;p[i]=0;
for(int j=0;j<20;j++){
jmp[i][j]=0;
}
}
}
}
Compilation message
jail.cpp: In function 'int main()':
jail.cpp:95:34: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
95 | if(path[j].size()>=i+1){
| ~~~~~~~~~~~~~~^~~~~
jail.cpp:101:25: warning: comparison of integer expressions of different signedness: 'std::set<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
101 | if(st.size()!=cnt){
| ~~~~~~~~~^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
