제출 #1135312

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1135312		ace5	Jail (JOI22_jail)	C++20	5 / 100	16 ms	3400 KiB

jail

#include <bits/stdc++.h>

using namespace std;

const int maxn = 120001;
const int maxlog = 19;

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

void add(int i,int x)
{
    //cout << "add " << i << ' ' << x << endl;
    for(int j = i+1;j <= n;j += ((j)&(-j)))
    {
        fenv[j] += x;
    }
}
int get(int l,int r)
{
   // cout << "get " << l << ' ' << r << endl;
    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];
    }
    //cout << ans << endl;
    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 {-1,-1};
    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 binup[maxlog][maxn];

void dfs1(int v,int p)
{
    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);
            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 get_sum(int u,int v)
{
   // cout << u << ' ' << v << ' ' << head[u] << ' ' << head[v] << endl;
    int ans =0;
    while(!isP(head[u],v))
    {
        //cout << u << endl;
        ans += get(tin[head[u]],tin[u]);
        u = par[head[u]];
    }
    while(!isP(head[v],u))
    {
       // cout << head[v] << ' ' << v << ' ' << tin[head[v]] << ' ' << tin[v] << endl;
        ans += get(tin[head[v]],tin[v]);
        //cout << v << endl;
        v = par[head[v]];
    }
   // cout << u << tin[u] << ' ' << tin[v] << "get_sum" << endl;
    ans += get(min(tin[u],tin[v]),max(tin[u],tin[v]));
    //cout << "t" << endl;
    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]];
    }
    //cout << tin[u] << ' ' << tin[v] << endl;
    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)
{
    if(!isP(v,u))
    {
        pair<int,int> xx = get(tin[v],tout[v]-1,0,n-1,0,0);
        if(xx.first > 0)
        {
            return st[itin[xx.second]];
        }
        pair<int,int> xx2 = get(tin[v],tout[v]-1,0,n-1,0,1);
        if(xx2.first > 0)
        {
            return en[itin[xx2.second]];
        }
    }
    else
    {
        for(int j = maxlog-1;j >= 0;--j)
        {
            if(!isP(binup[j][u],v))
                u = binup[j][u];
        }
        int pr = tin[u]-1;
        int sf = tout[u]+1;
        pair<int,int> xx = get(0,pr,0,n-1,0,0);
        if(xx.first > 0)
        {
            return st[itin[xx.second]];
        }
        pair<int,int> xx2 = get(0,pr,0,n-1,0,1);
        if(xx2.first > 0)
        {
            return en[itin[xx2.second]];
        }
        pair<int,int> xx3 = get(sf,n-1,0,n-1,0,0);
        if(xx3.first > 0)
        {
            return st[itin[xx3.second]];
        }
        pair<int,int> xx4 = get(sf,n-1,0,n-1,0,1);
        if(xx4.first > 0)
        {
            return en[itin[xx4.second]];
        }
    }
    return -1;
}

vector<int> ans;

void dfs3(int v)
{
    //cout << v << ' ' << "dfs3" << endl;
    vis[v] = 1;
    modify(tin[paths[v].first],0,0,n-1,0,0);
    modify(tin[paths[v].second],0,0,n-1,0,1);
    //cout << v << endl;
    while(true)
    {
       // cout << paths[v].first << ' ' << paths[v].second << endl;
        //cout << get(tin[3],tin[3],0,n-1,0,0).first << endl;
        int k = getv(paths[v].first,paths[v].second);
        //cout << k << endl;
        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 = 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);
        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;
            modify(tin[u],1,0,n-1,0,0);
            modify(tin[v],1,0,n-1,0,1);
        }
        //cout << "!" << endl;
        for(int i = 0;i < m;++i)
        {
            if(!vis[i])
            {
                dfs3(i);
            }
        }
        for(int i =0;i < m;++i)
        {
          //  cout << ans[i] << "!" << endl;
        }
      //  cout << "!" << endl;
        bool y = 1;
        for(int i = 0;i <= n;++i)
        {
            fenv[i] = 0;
        }
        for(int j = 0;j < m;++j)
        {
            //cout << tin[paths[j].first] << ' ';
            add(tin[paths[j].first],1);
        }
       // cout << endl;
       // cout << "!" << endl;
        for(int j = 0;j < m;++j)
        {
           // cout << j << endl;
            int tt = get_sum(paths[ans[j]].first,paths[ans[j]].second);
            //cout << tt << endl;
            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: 0 / 16
• Subtask 4: 0 / 28
• Subtask 5: 0 / 12
• Subtask 6: 0 / 11
• Subtask 7: 0 / 23