Submission #951099

#	Time	Username	Problem	Language	Result	Execution time	Memory
951099		hotboy2703	Jail (JOI22_jail)	C++14	100 / 100	2283 ms	563348 KiB

jail

#include<bits/stdc++.h>
using ll = long long;
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
#define MP make_pair
ll n,m;
const ll MAXN = 1.2e5;
const ll MAXK = 17;
ll cur_node;
namespace CYC{
    vector <ll> g[MAXN*MAXK*2 + MAXN * 5 + 100];
    void add_edge(ll u,ll v){g[u].push_back(v);}
    bool in[MAXN*MAXK*2 + MAXN * 5 + 100];
    bool in_st[MAXN*MAXK*2 + MAXN * 5 + 100];
    bool detect_cycle;
    void init(){
        for (ll i = 1;i <= cur_node;i++){g[i].clear();in[i] = 0;in_st[i] = 0;}
        detect_cycle = 0;
    }
    ll depth=0;
    ll cnt = 0;
    void dfs(ll u){
//        cout<<u<<' '<<depth<<' '<<cnt<<endl;
//        depth++;
//        cnt++;
        in_st[u] = 1;
        in[u] = 1;
        for (auto v:g[u]){
            if (in_st[v])detect_cycle = 1;
            if (in[v])continue;
            dfs(v);
        }
        in_st[u] = 0;
//        depth--;
    }
    void solve(){
        for (ll i = 1;i <= cur_node;i++)if (!in[i])dfs(i);
    }
}
vector <ll> g[MAXN+100];
ll sp[MAXK][MAXN+100];
ll node[MAXK][MAXN+100];
ll path[MAXN+100][2];
ll depth[MAXN+100];
ll lca(ll u,ll v){
    if (depth[u] > depth[v])swap(u,v);
    for (ll j = MAXK-1;j>=0;j--){
        if (depth[sp[j][v]]>=depth[u])v=sp[j][v];
    }
    if (v==u)return u;
    for (ll j = MAXK-1;j>=0;j--){
        if (sp[j][v] != sp[j][u]){
            v=sp[j][v];
            u=sp[j][u];
        }
    }
    return sp[0][u];
}
void dfs(ll u,ll p){
    sp[0][u] = p;
    depth[u] = depth[p]+1;
    for (auto v:g[u]){
        if (v==p)continue;
        dfs(v,u);
    }
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
    ll t;
    cin>>t;
    while (t--){
        cin>>n;
        for (ll i = 1;i <= n; i++){
            g[i].clear();

        }
        for (ll i = 1;i < n;i ++){
            ll u,v;
            cin>>u>>v;
            g[u].push_back(v);
            g[v].push_back(u);
        }
        cin>>m;
        for (ll i = 1;i <= m;i ++){
            ll s,t;
            cin>>s>>t;
            path[i][0] = s,path[i][1] = t;
        }
        dfs(1,1);
        for (ll j = 1;j < MAXK;j ++){
            for (ll i = 1;i <= n;i ++){
                sp[j][i] = sp[j-1][sp[j-1][i]];
//                cout<<sp[j][i]<<' ';
            }
//            cout<<'\n';
        }
//        exit(0);
        vector <pll> edge[2];
        cur_node = m + 1;
        for (ll k = 0;k < 2;k ++){
            for (ll i = 1;i <= n;i ++){
                node[0][i] = cur_node++;
            }
            for (ll j = 1;j < MAXK;j ++){
                for (ll i = 1;i <= n;i ++){
                    node[j][i] = cur_node++;
                    edge[k].push_back(MP(node[j][i],node[j-1][i]));
                    edge[k].push_back(MP(node[j][i],node[j-1][sp[j-1][i]]));
                }
            }
            for (ll i = 1;i <= m;i ++){
                edge[k].push_back(MP(node[0][path[i][k]],i));
            }
            for (ll i = 1;i <= m;i ++){
                ll u = path[i][0],v = path[i][1];
                ll x = lca(u,v);
//                cout<<u<<' '<<v<<' '<<x<<'\n';
                bool no_lca = 0;
                if (k==0){
                    if (u != x)u = sp[0][u];
                    else no_lca = 1;
                }
                if (k==1){
                    if (v != x)v = sp[0][v];
                    else no_lca = 1;
                }
                for (ll j = MAXK-1;j>=0;j--){
                    if (depth[u]-MASK(j) >= depth[x]){
//                        cout<<"U "<<i<<' '<<j<<'\n';
                        edge[k].push_back(MP(i,node[j][u]));
                        u = sp[j][u];
                    }
                    if (depth[v]-MASK(j) >= depth[x]){
//                        cout<<"V "<<i<<' '<<j<<'\n';
                        edge[k].push_back(MP(i,node[j][v]));
                        v = sp[j][v];
                    }
                }
                if (!no_lca)edge[k].push_back(MP(i,node[0][x]));
            }
        }
        CYC::init();
        for (ll j = 0;j < 2;j ++){
            for (auto x:edge[j]){
                if (j)swap(x.fi,x.se);
                CYC::add_edge(x.fi,x.se);
            }
        }
//        exit(0);
//        cout<<cur_node<<endl;
//        exit(0);
        CYC::solve();
        cout<<(CYC::detect_cycle?"No":"Yes")<<'\n';
    }
}

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