oj.uz

Submission #1013528

# Submission time Handle Problem Language Result Execution time Memory
1013528 2024-07-03T15:29:26 Z ReLice Jail (JOI22_jail) C++17
0 / 100
 74 ms 146768 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)){
            g[a+n*(i+1)].pb(x);
            g[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;
            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<=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
4
1 2
2 3
3 4
2
1 3
2 4

83 1
84 2
88 83
88 84


*/

Compilation message

jail.cpp: In function 'std::string solve()':
jail.cpp:154:33: warning: unused variable 'b' [-Wunused-variable]
  154 |             ll a=up[v[i].sc][0],b=x;
      |                                 ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 146004 KB Output is correct
2 Correct 57 ms 146000 KB Output is correct
3 Correct 56 ms 146260 KB Output is correct
4 Incorrect 68 ms 146768 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 146004 KB Output is correct
2 Correct 57 ms 146004 KB Output is correct
3 Incorrect 60 ms 146256 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 146004 KB Output is correct
2 Correct 57 ms 146004 KB Output is correct
3 Incorrect 60 ms 146256 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 146004 KB Output is correct
2 Correct 57 ms 146004 KB Output is correct
3 Incorrect 60 ms 146256 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 146004 KB Output is correct
2 Correct 57 ms 146004 KB Output is correct
3 Incorrect 60 ms 146256 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 145900 KB Output is correct
2 Correct 59 ms 146000 KB Output is correct
3 Correct 59 ms 146092 KB Output is correct
4 Correct 55 ms 146000 KB Output is correct
5 Incorrect 70 ms 146256 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 146004 KB Output is correct
2 Correct 57 ms 146000 KB Output is correct
3 Correct 56 ms 146260 KB Output is correct
4 Incorrect 68 ms 146768 KB Output isn't correct
5 Halted 0 ms 0 KB -