Submission #902927

#	Time	Username	Problem	Language	Result	Execution time	Memory
902927		Tuanlinh123	Jail (JOI22_jail)	C++17	0 / 100	5072 ms	95336 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];
ll check[maxn], cnt[maxn];
ll dis[maxn], lca[maxn], u[maxn], v[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(), cnt[i]=0, check[i]=0;
        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]))
                    cnt[j]++;
        ll ans=0;
        priority_queue <pll, vector <pll>, greater<pll>> q;
        for (ll i=1; i<=m; i++)
            q.push({cnt[i], i});
        while (!q.empty())
        {
            ll i=q.top().se, cnti=q.top().fi; q.pop();
            if (cnti!=cnt[i] || cnti || check[i]) continue;
            check[i]=1; ans++;
            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]))
                    cnt[j]--;
                if (i!=j && dist(u[j], v[i])+dist(v[i], v[j])==dist(u[j], v[j]))
                    cnt[j]++;
                if (cnt[j]==0 && !check[j])
                    q.push({cnt[j], j});
            }
        }
        if (ans==m) cout << "Yes\n";
        else cout << "No\n";
    }
}

Compilation message (stderr)

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

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