Submission #632456

#	Time	Username	Problem	Language	Result	Execution time	Memory
632456		Mahdi	Jail (JOI22_jail)	C++17	0 / 100	3 ms	5972 KiB

jail

    #include<bits/stdc++.h>
    #pragma GCC optimize("Ofast")
    using namespace std;
    #define all(v) v.begin(), v.end()
    #define F first
    #define S second
    typedef pair<int, int> pii;
    typedef long long ll;
    const int N=12e4+5;
    int n, m, s[N], t[N], pr[N][18], dis[N];
    vector<int>g[N], h[N], nd;
    bool mk[N];
    pii st[N];
     
    void dfs(const int &v, const int &p=-1){
        for(int u: g[v]){
            if(u!=p){
                pr[u][0]=v;
                for(int i=1;i<17;++i)
                    pr[u][i]=pr[pr[u][i-1]][i-1];
                dis[u]=dis[v]+1;
                dfs(u, v);
            }   
        }
    }
     
    int par(int v, int p){
        for(int i=0;p>0;++i){
            if(p&1)
                v=pr[v][i];
            p>>=1;
        }
        return v;
    }
     
    int lca(int u, int v){
        u=par(u, dis[u]-dis[v]);
        v=par(v, dis[v]-dis[u]);
        if(u==v)
            return v;
        for(int i=16;i>=0;--i){
            if(pr[u][i]!=pr[v][i]){
                v=pr[v][i];
                u=pr[u][i];
            }
        }
        return pr[v][0];
    }
     
    void sfd(const int &v){
        mk[v]=1;
        for(int u: h[v]){
            if(!mk[u])
                sfd(u);
        }
        nd.push_back(v);
    }
     
    void sol(){
        cin>>n;
        for(int i=0;i<n;++i)
            g[i].clear();
        for(int i=1;i<n;++i){
            int u, v;
            cin>>u>>v;
            g[--u].push_back(--v);
            g[v].push_back(u);
        }
        cin>>m;
        memset(s, -1, 4*n);
//        memset(t, -1, 4*n);
        for(int i=0;i<m;++i){
            int u, v;
            cin>>u>>v;
            s[--u]=i;
            t[--v]=i;
            st[i]={u, v};
        }
        dfs(0);
        for(int i=0;i<m;++i)
            h[i].clear();
        for(int i=0;i<m;++i){
            int u=st[i].F;
            int v=st[i].S;
            int w=lca(u, v);
            int x=u;
            while(true){
                if(s[x]!=-1 && s[x]!=i)
                    h[s[x]].push_back(i);
                if(t[x]!=-1 && t[x]!=i)
                    h[i].push_back(t[x]);
                if(x==w)
                    break;
                x=pr[x][0];
            }
            x=v;
            while(true){
                if(s[x]!=-1 && s[x]!=i)
                    h[s[x]].push_back(i);
                if(t[x]!=-1 && t[x]!=i)
                    h[i].push_back(t[x]);
                if(x==w)
                    break;
                x=pr[x][0];
            }
        }
        nd.clear();
        memset(mk, 0, m);
        for(int i=0;i<m;++i){
            if(!mk[i])
                sfd(i);
        }
        memset(mk, 0, m);
        for(int i=0;i<m;++i){
            mk[nd[i]]=1;
            for(int u: h[nd[i]]){
                if(!mk[u]){
                    cout<<"NO\n";
                    return;
                }
            }
        }
        cout<<"YES\n";
    }
     
    int main(){
        ios_base::sync_with_stdio(0); cin.tie(0);
        int T;
        cin>>T;
        while(T--)
            sol();
    }

Compilation message (stderr)

In file included from /usr/include/string.h:495,
                 from /usr/include/c++/10/cstring:42,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:48,
                 from jail.cpp:1:
In function 'void* memset(void*, int, size_t)',
    inlined from 'void sol()' at jail.cpp:108:15:
/usr/include/x86_64-linux-gnu/bits/string_fortified.h:71:33: warning: 'void* __builtin___memset_chk(void*, int, long unsigned int, long unsigned int)' specified size between 18446744071562067968 and 18446744073709551615 exceeds maximum object size 9223372036854775807 [-Wstringop-overflow=]
   71 |   return __builtin___memset_chk (__dest, __ch, __len, __bos0 (__dest));
      |          ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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