Submission #1135326

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135326		ace5	Jail (JOI22_jail)	C++20	49 / 100	48 ms	5448 KiB

jail

#include <bits/stdc++.h>

using namespace std;

const int maxn = 120005;
const int maxlog = 19;
const int INF = 200000;

pair<int,int> segTree[3][maxn];
int fenv[maxn];
int n;

void add(int i,int x)
{
    for(int j = i+1;j <= n;j += ((j)&(-j)))
    {
        fenv[j] += x;
    }
}
int get(int l,int r)
{
    r++;
    int ans = 0;
    for(int j = r;j > 0;j -= ((j)&(-j)))
    {
        ans += fenv[j];
    }
    for(int j = l;j > 0;j -= ((j)&(-j)))
    {
        ans -= fenv[j];
    }
    return ans;
}

void modify(int i,int x,int l,int r,int indV,int j)
{
    if(l > i || r < i)
        return ;
    else if(l == r)
    {
        segTree[j][indV] = {x,l};
        return ;
    }
    int m = (l+r)/2;
    modify(i,x,l,m,indV*2+1,j);
    modify(i,x,m+1,r,indV*2+2,j);
    segTree[j][indV] = max(segTree[j][indV*2+1],segTree[j][indV*2+2]);
    return ;
}
pair<int,int> get(int lx,int rx,int l,int r,int indV,int j)
{
    if(l > rx || r < lx)
        return {-INF,-INF};
    else if(l >= lx && r <= rx)
    {
        return segTree[j][indV];
    }
    int m = (l+r)/2;
    pair<int,int> sl = get(lx,rx,l,m,indV*2+1,j);
    pair<int,int> sr = get(lx,rx,m+1,r,indV*2+2,j);
    return max(sl,sr);
}

int st[maxn],en[maxn];
int head[maxn],sz[maxn];
vector<int> g[maxn];
int par[maxn];
int tin[maxn],tout[maxn];
int itin[maxn];
vector<pair<int,int>> paths;
int times = 0;
int vis[maxn];
int dep[maxn];
int binup[maxlog][maxn];

void dfs1(int v,int p,int d)
{
    dep[v] = d;
    sz[v] = 1;
    par[v] = p;
    for(int i = 0;i < g[v].size();++i)
    {
        if(g[v][i] != p)
        {
            dfs1(g[v][i],v,d+1);
            sz[v] += sz[g[v][i]];
            if(g[v][0] == p || sz[g[v][i]] > sz[g[v][0]])
                swap(g[v][i],g[v][0]);
        }
    }
    return ;
}

void dfs2(int v,int p,int th)
{
    head[v] = th;
    tin[v] = times++;
    itin[tin[v]] = v;
    for(int i = 0;i < g[v].size();++i)
    {
        if(g[v][i] != p)
        {
            dfs2(g[v][i],v,(i == 0 ? th : g[v][i]));
        }
    }
    tout[v] = times;
    return ;
}


bool isP(int u,int v)
{
    return tin[u] <= tin[v] && tout[v] <= tout[u];
}

int lca(int u,int v)
{
    for(int j = maxlog-1;j >= 0;--j)
    {
        if(!isP(binup[j][u],v))
            u = binup[j][u];
    }
    return (isP(u,v) ? u : par[u]);
}

int get_sum(int u,int v)
{
    int ans =0;
    while(!isP(head[u],v))
    {
        ans += get(tin[head[u]],tin[u]);
        u = par[head[u]];
    }
    while(!isP(head[v],u))
    {
        ans += get(tin[head[v]],tin[v]);
        v = par[head[v]];
    }
    ans += get(min(tin[u],tin[v]),max(tin[u],tin[v]));
    return ans;
}

int getv(int u,int v)
{
    while(!isP(head[u],v))
    {
        pair<int,int> xx = get(tin[head[u]],tin[u],0,n-1,0,0);
        if(xx.first > 0)
        {
            return st[itin[xx.second]];
        }
        u = par[head[u]];
    }
    while(!isP(head[v],u))
    {
        pair<int,int> xx = get(tin[head[v]],tin[v],0,n-1,0,0);
        if(xx.first > 0)
        {
            return st[itin[xx.second]];
        }
        v = par[head[v]];
    }
    pair<int,int> xx = get(min(tin[u],tin[v]),max(tin[u],tin[v]),0,n-1,0,0);
    if(xx.first > 0)
    {
        return st[itin[xx.second]];
    }
    else
        return -1;
}
int geten(int u,int v)
{
    pair<int,int> cc = get(tin[v],tout[v]-1,0,n-1,0,1);
   // cout << cc.first << ' ' << -dep[v] << ' ' << v << endl;
    if(cc.first >= -dep[v])
    {
        return st[itin[cc.second]];
    }
    pair<int,int> cc2 = get(tin[v],tout[v]-1,0,n-1,0,2);
    if(cc2.first >= -dep[v])
    {
        return en[itin[cc2.second]];
    }
    return -1;
}

vector<int> ans;

void dfs3(int v)
{
    vis[v] = 1;
    modify(tin[paths[v].first],0,0,n-1,0,0);
    modify(tin[paths[v].first],-INF,0,n-1,0,1);
    modify(tin[paths[v].second],-INF,0,n-1,0,2);
    while(true)
    {
        int k = getv(paths[v].first,paths[v].second);
        if(k != -1)
        {
            dfs3(k);
        }
        else
        {
            break;
        }
    }
    while(true)
    {
        int k = geten(paths[v].first,paths[v].second);
        if(k != -1)
        {
            dfs3(k);
        }
        else
        {
            break;
        }
    }
    ans.push_back(v);
    return ;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int q;
    cin >> q;
    while(q--)
    {
        cin >> n;
        paths.clear();
        ans.clear();
        times = 0;
        for(int i = 1;i < 3;++i)
        {
            for(int j  =0;j < 4*n;++j)
                segTree[i][j] = {-INF,0};
        }
        for(int i = 0;i < n;++i)
        {
            g[i].clear();
            st[i] = -1;
            en[i] = -1;
        }
        for(int i = 0;i < n-1;++i)
        {
            int u,v;
            cin >> u >> v;
            u--;
            v--;
            g[u].push_back(v);
            g[v].push_back(u);
        }
      //  cout << "!" << endl;
        dfs1(0,0,0);
        dfs2(0,-1,0);
        for(int j = 0;j < maxlog;++j)
        {
            for(int i = 0;i < n;++i)
            {
                binup[j][i] = (j == 0 ? par[i] : binup[j-1][binup[j-1][i]]);
            }
        }
        int m;
        cin >> m;
        for(int i = 0;i < m;++i)
        {
            int u,v;
            cin >> u >> v;
            u--;
            v--;
            st[u] = i;
            en[v] = i;
            paths.push_back({u,v});
            vis[i] = 0;
            int lc = lca(u,v);
            modify(tin[u],1,0,n-1,0,0);
            modify(tin[u],-dep[lc],0,n-1,0,1);
            modify(tin[v],-dep[lc],0,n-1,0,2);
        }
        for(int i = 0;i < m;++i)
        {
            if(!vis[i])
            {
                dfs3(i);
            }
        }
       // for(int i = 0;i < m;++i)
       // {
       //     cout << ans[i] << endl;
       // }
        bool y = 1;
        for(int i = 0;i <= n;++i)
        {
            fenv[i] = 0;
        }
        for(int j = 0;j < m;++j)
        {
            add(tin[paths[j].first],1);
        }
        for(int j = 0;j < m;++j)
        {
            int tt = get_sum(paths[ans[j]].first,paths[ans[j]].second);
            y &= (tt == 1);
            add(tin[paths[ans[j]].first],-1);
            add(tin[paths[ans[j]].second],1);
        }
        cout << (y ? "Yes\n" : "No\n");
    }
}

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