| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1013558 |
2024-07-03T16:18:52 Z |
ReLice |
Jail (JOI22_jail) |
C++17 |
|
58 ms |
146040 KB |
#include <bits/stdc++.h>
#define ll long long
#define str string
#define ins insert
#define ld long double
#define pb push_back
#define pf push_front
#define pof pop_front()
#define pob pop_back()
#define lb lower_bound
#define ub upper_bound
#define endl "\n"
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define sz size()
#define vll vector<ll>
#define bc back()
#define arr array
#define pll vector<pair<ll,ll>>
using namespace std;/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>*/
template<class S,class T>
bool chmin(S &a,const T &b) {
return a>b?(a=b)==b:false;
}
template<class S,class T>
bool chmax(S &a,const T &b) {
return a<b?(a=b)==b:false;
}
//void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
void start(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
const ll inf=1e18;
const ll mod=998244353;
const ll N=1.2e5+7;
const ld eps=1e-9;
vector<vll> g(N);
vector<vll> g2(N*50);
ll vis[N*50];
ll up[N][20],d[N];
ll mx;
bool flag;
ll n;
vll s(N),t(N);
void dfs(ll v){
chmax(mx,d[v]);
for(ll i=1;i<20;i++) up[v][i]=up[up[v][i-1]][i-1];
for(auto i : g[v]){
if(i==up[v][0])continue;
up[i][0]=v;
d[i]=d[v]+1;
dfs(i);
}
}
ll lca(ll a,ll b,ll x){
if(d[a]<d[b])swap(a,b);
for(ll i=19;i>=0;i--){
if(d[a]-d[b]>(1ll<<i)){
a=up[a][i];
}
}
if(up[a][0]==b)return a;
a=up[a][0];
for(ll i=19;i>=0;i--){
if(d[a]>(1ll<<i) && up[a][i]!=up[b][i]){
a=up[a][i];
b=up[b][i];
}
}
return a;
}
void build(ll a,ll p,ll x){
p=d[a]-d[p];
for(ll i=19;i>=0;i--){
if(p>=(1ll<<i)){
//cout<<a<<'*'<<i<<endl;
g2[a+n*(i+1)].pb(x);
g2[x].pb(a+n*(20+i+1));
a=up[a][i];
p-=(1ll<<i);
}
}
}
bool f[N*50];
void check(ll v){
f[v]=1;
vis[v]=1;
if(flag)return;
for(auto i : g2[v]){
if(f[i])flag=true;
else if(vis[i])continue;
if(flag){f[v]=0;return;}
check(i);
}
f[v]=0;
}
str solve(){
ll i,j;
cin>>n;
flag=0;
for(i=0;i<=n;i++){
g[i].clear();
vis[i]=0;
t[i]=s[i]=0;
for(j=0;j<20;j++)up[i][j]=0;
}
ll a,b;
for(i=1;i<n;i++){
cin>>a>>b;
g[a].pb(b);
g[b].pb(a);
}
d[1]=1;
dfs(1);
ll m;
cin>>m;
for(i=1;i<=n*40;i++)g2[i].clear();
vector<pair<ll,ll> > v(1);
for(i=0;i<m;i++){
cin>>a>>b;
s[a]=i+1;
t[b]=i+1;
v.pb({a,b});
}
for(i=1;i<=n;i++){
if(s[i])g2[s[i]].pb(i+n);
if(t[i])g2[i+n*21].pb(t[i]);
}
for(j=1;j<19;j++){
for(i=1;i<=n;i++){
if(d[i]<(1ll<<(j))) continue;
ll p=up[i][j-1];
g2[i+n*j].pb(i+n*(j+1));
g2[p+n*j].pb(i+n*(j+1));
g2[i+n*(20+j+1)].pb(i+n*(20+j));
g2[i+n*(20+j+1)].pb(p+n*(20+j));
}
}
for(i=1;i<=m;i++){
ll x=lca(v[i].fr,v[i].sc,i),lc=up[x][0];
g2[v[i].sc+n].pb(i);
g2[i].pb(v[i].fr+n*21);
if(d[v[i].fr]>d[v[i].sc])swap(v[i].fr,v[i].sc);
if(lc==v[i].fr){
if(up[v[i].sc][0]==v[i].fr)continue;
ll a=up[v[i].sc][0],b=x;
//cout<<a<<' '<<x<<endl;
build(a,x,i);
}else {
x=lc;
ll a=up[v[i].fr][0],b=up[v[i].sc][0];
build(a,lc,i);
build(b,lc,i);
}
g2[x+n].pb(i);
g2[i].pb(x+n*21);
}
for(i=1;i<45*n;i++){
for(auto j : g2[i])cout<<i<<' '<<j<<endl;
}
for(i=1;i<=m;i++){
if(!vis[i]){
check(i);
if(flag)return "No";
}
}
return "Yes";
}
signed main(){
start();
ll t=1;
cin>>t;
while(t--) cout<<solve()<<endl;
return 0;
}
/*
1
5
1 2
2 3
3 4
4 5
2
1 3
5 1
*/
Compilation message
jail.cpp: In function 'std::string solve()':
jail.cpp:155:33: warning: unused variable 'b' [-Wunused-variable]
155 | ll a=up[v[i].sc][0],b=x;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
58 ms |
146000 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
57 ms |
146040 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
57 ms |
146040 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
57 ms |
146040 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
57 ms |
146040 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
57 ms |
146000 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
58 ms |
146000 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
