Submission #631335

#	Time	Username	Problem	Language	Result	Execution time	Memory
631335		mdn2002	Jail (JOI22_jail)	C++14	21 / 100	5093 ms	948 KiB

jail

#include<bits/stdc++.h>
using namespace std;
int n , m , is [502] , st [502] , fn [502] , ff;
vector < int > gr [502] , v , pth;
void go ( int x , int p , int pr )
{
    pth . push_back ( x );
    if ( fn [pr] == x )
    {
        for ( auto u : pth )
        {
            if ( is [u] == 1 && u != st [pr] ) ff = 1;
        }
        is [ st [pr] ] = 0;
        is [ fn [pr] ] = 1;
    }
    for ( auto u : gr [x] )
    {
        if ( u == p ) continue;
        go ( u , x , pr );
    }

    pth . pop_back ();
}
bool ck ( )
{
    ff = 0;
    for ( int i = 1 ; i <= n ; i ++ ) is [i] = 0;
    for ( int i = 1 ; i <= m ; i ++ ) is [ st [i] ] = 1;
    for ( auto x : v )
    {
        go ( st [x] , 0 , x );
    }
    if ( ff ) return 0;
    return 1;
}
int main()
{
    int q;
    cin >> q;
    while ( q -- )
    {
        cin >> n;
        for ( int i = 1 ; i <= n ; i ++ )
        {
            gr [i] . clear ();
            is [i] = 0;
        }
        for ( int i = 0 ; i < n - 1 ; i ++ )
        {
            int x , y;
            cin >> x >> y;
            gr [x] . push_back ( y );
            gr [y] . push_back ( x );
        }
        cin >> m;
        v . clear ();
        for ( int i = 1 ; i <= m ; i ++ )
        {
            v . push_back ( i );
            cin >> st [i] >> fn [i];
        }
        int f = 0;
        do
        {
            f = max ( f , ( int ) ck () );
        } while ( next_permutation( v . begin () , v . end () ) );
        if ( f ) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
}

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