Submission #584766

#	Time	Username	Problem	Language	Result	Execution time	Memory
584766		azberjibiou	Jail (JOI22_jail)	C++17	61 / 100	5057 ms	26312 KiB

jail

#include <bits/stdc++.h>
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fir first
#define sec second
#define pdd pair<long double, long double>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ld long double
#define pmax pair<__int128, __int128>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
typedef long long ll;
typedef unsigned int uint;
using namespace std;
int dx[4]= {0, 1, 0, -1}, dy[4]= {1, 0, -1, 0};
int ddx[8]={1, 1, 0, -1, -1, -1, 0, 1}, ddy[8]={0, 1, 1, 1, 0, -1, -1, -1};
const int mxN=120005;
const int mxM=300005;
const int mxK=1000000000;
const int MOD=1e9+7;
const ll INF=1000000000000000005;
int N, M;
vector <int> v[mxN];
pii A[mxN];
vector <int> dag[mxN];
int dep[mxN];
int sps[mxN][20];
int deg[mxN];
queue <int> que;
void init()
{
    for(int i=1;i<=N;i++)   v[i].clear();
    for(int i=1;i<=M;i++)   dag[i].clear();
    for(int i=1;i<=M;i++)   deg[i]=0;
    while(que.size())   que.pop();
}
void dfs(int now, int pre)
{
    for(int nxt : v[now])   if(nxt!=pre)
    {
        dep[nxt]=dep[now]+1;
        sps[nxt][0]=now;
        dfs(nxt, now);
    }
}
void make_sparse()
{
    for(int z=1;z<20;z++)
    {
        for(int i=1;i<=N;i++)
        {
            sps[i][z]=sps[sps[i][z-1]][z-1];
        }
    }
}
int lca(int a, int b)
{
    if(dep[a]<dep[b])   swap(a, b);
    for(int i=19;i>=0;i--)
    {
        if(dep[a]-(1<<i)>=dep[b])   a=sps[a][i];
    }
    if(a==b)    return a;
    for(int i=19;i>=0;i--)
    {
        if(sps[a][i]!=sps[b][i])    a=sps[a][i], b=sps[b][i];
    }
    return sps[a][0];
}
bool on(int a, int b, int c)
{
    int lcaab=lca(a, b), lcaac=lca(a, c), lcabc=lca(b, c);
    if(lcabc==a)    return true;
    if(lcaab==a && lcaac==lcabc)    return true;
    if(lcaac==a && lcaab==lcabc)    return true;
    return false;
}
int main()
{
    gibon
    int T;
    cin >> T;
    while(T--)
    {
        cin >> N;
        for(int i=1;i<N;i++)
        {
            int a, b;
            cin >> a >> b;
            v[a].push_back(b);
            v[b].push_back(a);
        }
        dfs(1, -1);
        make_sparse();
        cin >> M;
        for(int i=1;i<=M;i++)   cin >> A[i].fir >> A[i].sec;
        for(int i=1;i<=M;i++)
        {
            for(int j=1;j<=M;j++)   if(i!=j)
            {
                if(on(A[j].fir, A[i].fir, A[i].sec))    dag[i].push_back(j), deg[j]++;
                if(on(A[j].sec, A[i].fir, A[i].sec))    dag[j].push_back(i), deg[i]++;
            }
        }
        int cnt=0;
        for(int i=1;i<=M;i++)   if(deg[i]==0)  que.push(i);
        while(que.size())
        {
            int now=que.front();
            que.pop();
            cnt++;
            for(int nxt : dag[now])
            {
                deg[nxt]--;
                if(!deg[nxt])   que.push(nxt);
            }
        }
        cout << (cnt==M ? "Yes" : "No") << '\n';
        init();
    }
}

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