Submission #902992

#	Time	Username	Problem	Language	Result	Execution time	Memory
902992		Tuanlinh123	Jail (JOI22_jail)	C++17	61 / 100	5098 ms	99716 KiB

jail

#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
using namespace std;

const ll maxn=120005;
pll sp[20][maxn*2];
vector <pll> euler;
vector <ll> A[maxn], B[maxn];
ll dis[maxn], lca[maxn], u[maxn], v[maxn], deg[maxn];

void dfs(ll u, ll pa)
{
    lca[u]=euler.size()+1;
    euler.pb({lca[u], u});
    for (ll v:A[u])
    {
        if (v==pa)
            continue;
        dis[v]=dis[u]+1, dfs(v, u);
        euler.pb({lca[u], u});
    }
}

void initsparse()
{
    ll n=euler.size();
    for (ll i=0; i<n; i++)
        sp[0][i+1]=euler[i];
    for (ll i=1; i<20; i++)
        for (ll j=1; j+(1<<i)<=n+1; j++)
            sp[i][j]=min(sp[i-1][j], sp[i-1][j+(1<<i-1)]);
}

ll dist(ll u, ll v)
{
    ll l=lca[u], r=lca[v];
    if (l>r) swap(l, r);
    ll j=__lg(r-l+1), p=min(sp[j][l], sp[j][r-(1<<j)+1]).se;
    return dis[u]+dis[v]-dis[p]*2;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll t; cin >> t;
    while (t--)
    {
        ll n; cin >> n;
        for (ll i=1; i<=n; i++)
            A[i].clear(), deg[i]=0, B[i].clear();
        euler.clear();
        for (ll i=1; i<n; i++)
        {
            ll u, v; cin >> u >> v;
            A[u].pb(v); A[v].pb(u);
        }
        dfs(1, 0); initsparse();
        ll m; cin >> m;
        for (ll i=1; i<=m; i++)
            cin >> u[i] >> v[i];
        for (ll i=1; i<=m; i++)
            for (ll j=1; j<=m; j++)
            {
                if (i!=j && dist(u[j], u[i])+dist(u[i], v[j])==dist(u[j], v[j]))
                    B[i].pb(j), deg[j]++;
                if (i!=j && dist(u[j], v[i])+dist(v[i], v[j])==dist(u[j], v[j]))
                    B[j].pb(i), deg[i]++;
            }
        queue <ll> q;
        for (ll i=1; i<=m; i++)
            if (deg[i]==0)
                q.push(i);
        while (!q.empty())
        {
            ll u=q.front(); q.pop();
            for (ll v:B[u])
            {
                deg[v]--;
                if (!deg[v]) q.push(v);
            }
        }
        bool ok=1;
        for (ll i=1; i<=m; i++)
            if (deg[i]) ok=0;
        if (ok) cout << "Yes\n";
        else cout << "No\n";
    }
}

Compilation message (stderr)

jail.cpp: In function 'void initsparse()':
jail.cpp:37:53: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   37 |             sp[i][j]=min(sp[i-1][j], sp[i-1][j+(1<<i-1)]);
      |                                                    ~^~

• Subtask 1: 0 / 5
• Subtask 2: 5 / 5
• Subtask 3: 16 / 16
• Subtask 4: 28 / 28
• Subtask 5: 12 / 12
• Subtask 6: 0 / 11
• Subtask 7: 0 / 23