Submission #903295

#	Time	Username	Problem	Language	Result	Execution time	Memory
903295		Tuanlinh123	Jail (JOI22_jail)	C++17	0 / 100	112 ms	179280 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;
vector <pll> euler;
pll sp[20][maxn*2];
vector <ll> A[maxn], B[maxn*50];
ll st[maxn], en[maxn], u[maxn], v[maxn];
ll n, m, jump[20][maxn], dep[maxn], lca[maxn];
ll Time, crr, lo[maxn*50], num[maxn*50], comp[maxn*50];
stack <ll> s;

ll to_idx(ll i, ll u, ll t)
{
    return (u*20+i)*2+t+n;
}

string debug(ll idx)
{
    if (idx<=n) return to_string(idx);
    ll t=(idx-n)%2, i=((idx-n)/2)%20, u=((idx-n)/2)/20;
    return "("+to_string(i)+","+to_string(u)+","+to_string(t)+")";
}

void insert(ll u, ll v)
{
    B[u].pb(v);
}

void dfs(ll u, ll pa)
{
    jump[0][u]=pa;
    if (st[u]) insert(to_idx(0, u, 1), st[u]);
    if (en[u]) insert(en[u], to_idx(0, u, 0));
    lca[u]=euler.size()+1;
    euler.pb({lca[u], u});
    for (ll i=1; jump[i-1][jump[i-1][u]]; i++)
    {
        jump[i][u]=jump[i-1][jump[i-1][u]];
        insert(to_idx(i, u, 1), to_idx(i-1, u, 1));
        insert(to_idx(i, u, 1), to_idx(i-1, jump[i-1][u], 1));
        insert(to_idx(i-1, u, 0), to_idx(i, u, 0));
        insert(to_idx(i-1, jump[i-1][u], 0), to_idx(i, u, 0));
    }
    for (ll v:A[u])
    {
        if (v==pa) continue;
        dep[v]=dep[u]+1, dfs(v, u);
        euler.pb({lca[u], u});
    }
}

void sparse()
{
    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 LCA(ll u, ll v)
{
    ll l=lca[u], r=lca[v];
    if (l>r) swap(l, r);
    ll j=__lg(r-l+1);
    return min(sp[j][l], sp[j][r-(1<<j)+1]).se;
}

void addedge(ll u, ll dis, ll idx)
{
    for (ll i=0; i<20; i++)
        if (dis&1<<i)
        {
            insert(idx, to_idx(i, u, 1));
            insert(to_idx(i, u, 0), idx);
            u=jump[i][u];
        }
}

void add(ll u, ll v, ll idx)
{
    ll p=LCA(u, v);
    addedge(u, dep[u]-dep[p]+1, idx);
    addedge(v, dep[v]-dep[p], idx);
}

void dfs2(ll u)
{
    s.push(u);
    lo[u]=num[u]=++Time;
    for (ll v:B[u])
    {
        if (num[v]) lo[u]=min(lo[u], num[v]);
        else
        {
            dfs2(v); 
            lo[u]=min(lo[u], lo[v]);
        }
    }
    if (lo[u]==num[u])
    {
        crr++;
        while (s.top()!=u)
            comp[s.top()]=crr, num[s.top()]=1e9, s.pop();
        comp[s.top()]=crr, num[s.top()]=1e9, s.pop();
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll t; cin >> t;
    while (t--)
    {
        cin >> n; Time=crr=0; euler.clear();
        for (ll i=1; i<=n; i++)
        {
            A[i].clear();
            st[i]=en[i]=u[i]=v[i]=0;
        }
        for (ll i=1; i<=n*50; i++)
        {
            B[i].clear();
            lo[i]=num[i]=comp[i]=0;
        }
        for (ll i=1; i<n; i++)
        {
            ll u, v; cin >> u >> v;
            A[u].pb(v); A[v].pb(u);
        }
        cin >> m;
        for (ll i=1; i<=m; i++)
        {
            cin >> u[i] >> v[i];
            st[u[i]]=i, en[v[i]]=i;
        }
        dfs(1, 0); sparse();
        for (ll i=1; i<=m; i++)
            add(u[i], v[i], i);
        for (ll i=1; i<=n*50; i++)
            if (!num[i]) dfs2(i);
        vector <ll> val;
        for (ll i=1; i<=m; i++) val.pb(comp[i]);
        val.resize(unique(val.begin(), val.end())-val.begin());
        if (val.size()==m) cout << "Yes\n";
        else cout << "No\n";
    }
}

Compilation message (stderr)

jail.cpp: In function 'void sparse()':
jail.cpp:67:53: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   67 |             sp[i][j]=min(sp[i-1][j], sp[i-1][j+(1<<i-1)]);
      |                                                    ~^~
jail.cpp: In function 'int main()':
jail.cpp:155:23: 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]
  155 |         if (val.size()==m) cout << "Yes\n";
      |             ~~~~~~~~~~^~~

• 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