oj.uz

답안 #632453

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
632453 2022-08-20T05:01:06 Z Mahdi Jail (JOI22_jail) C++17
0 / 100
 4 ms 5976 KB 
#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

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:11:
/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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 5972 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 5976 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 5976 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 5976 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 5976 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 5972 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 5972 KB Output isn't correct
2 Halted 0 ms 0 KB -