oj.uz

Submission #1001137

# Submission time Handle Problem Language Result Execution time Memory
1001137 2024-06-18T15:24:41 Z De3b0o Jail (JOI22_jail) C++14
21 / 100
 5000 ms 14468 KB 
#include<bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define in insert
#define pb push_back
#define ppb pop_back()
#define d3 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define cans cout << ans << "\n";
#define yes cout << "Yes" << "\n";
#define no cout << "No" << "\n";
#define pll pair<ll,ll>
#define lin cout << "\n";
#define mod 1000000007
#define mid ((l+r)/2)
#define lc (2*x)
#define rc (2*x+1)

using namespace std;

ll n , m;
vector<ll> adj[120009];
ll S[120009] , T[120009];
vector<ll> path[120009];
set<ll> pas[120009];
ll pr[120009];

void dfs(ll x , ll p , ll f , ll s)
{
    pr[x]=p;
    if(x==f)
    {
        ll y = f;
        while(y)
        {
            path[s].pb(y);
            pas[s].in(y);
            y=pr[y];
        }
        reverse(path[s].begin(),path[s].end());
        return;
    }
    for(auto it : adj[x])
    {
        if(it==p)
            continue;
        dfs(it,x,f,s);
    }
}

int main()
{
    d3
    ll t;
    cin >> t;
    while(t--)
    {
        cin >> n;
        for(int i = 1 ; n>=i ; i++)
            adj[i].clear();
        for(int i = 0 ; n-1>i ; i++)
        {
            ll u , v;
            cin >> u >> v;
            adj[u].pb(v);
            adj[v].pb(u);
        }
        cin >> m;
        for(int i = 1 ; m>=i ; i++)
        {
            cin >> S[i] >> T[i];
            path[i].clear();
            pas[i].clear();
            dfs(S[i],0,T[i],i);
        }
        bool ans = 0;
        ll a[m];
        for(int i = 0 ; m>i ; i++)
            a[i]=i+1;
        do
        {
            bool g = 1;
            for(int i = 0 ; m>i ; i++)
            {
                for(int j = i+1 ; m>j ; j++)
                {
                    if(pas[a[i]].find(S[a[j]])!=pas[a[i]].end())
                        g=0;
                }
                for(int j = i-1 ; j>=0 ; j--)
                {
                    if(pas[a[i]].find(T[a[j]])!=pas[a[i]].end())
                        g=0;
                }
            }
            if(g)
                ans=1;
        }
        while(next_permutation(a,a+m));
        if(ans)
            yes
        else
            no
    }
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14168 KB Output is correct
2 Correct 3 ms 14172 KB Output is correct
3 Correct 3 ms 14172 KB Output is correct
4 Correct 9 ms 14172 KB Output is correct
5 Correct 18 ms 14172 KB Output is correct
6 Correct 3 ms 14428 KB Output is correct
7 Correct 9 ms 14428 KB Output is correct
8 Execution timed out 5098 ms 14428 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14172 KB Output is correct
2 Correct 2 ms 14172 KB Output is correct
3 Correct 4 ms 14428 KB Output is correct
4 Correct 5 ms 12424 KB Output is correct
5 Correct 4 ms 14168 KB Output is correct
6 Correct 4 ms 14172 KB Output is correct
7 Correct 4 ms 14172 KB Output is correct
8 Correct 3 ms 14172 KB Output is correct
9 Correct 3 ms 14168 KB Output is correct
10 Correct 3 ms 14384 KB Output is correct
11 Correct 3 ms 14168 KB Output is correct
12 Correct 2 ms 14168 KB Output is correct
13 Correct 3 ms 14336 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14172 KB Output is correct
2 Correct 2 ms 14172 KB Output is correct
3 Correct 4 ms 14428 KB Output is correct
4 Correct 5 ms 12424 KB Output is correct
5 Correct 4 ms 14168 KB Output is correct
6 Correct 4 ms 14172 KB Output is correct
7 Correct 4 ms 14172 KB Output is correct
8 Correct 3 ms 14172 KB Output is correct
9 Correct 3 ms 14168 KB Output is correct
10 Correct 3 ms 14384 KB Output is correct
11 Correct 3 ms 14168 KB Output is correct
12 Correct 2 ms 14168 KB Output is correct
13 Correct 3 ms 14336 KB Output is correct
14 Correct 3 ms 14172 KB Output is correct
15 Correct 2 ms 14172 KB Output is correct
16 Correct 12 ms 14428 KB Output is correct
17 Correct 5 ms 14428 KB Output is correct
18 Correct 10 ms 14428 KB Output is correct
19 Correct 2 ms 14172 KB Output is correct
20 Correct 9 ms 14428 KB Output is correct
21 Correct 7 ms 14428 KB Output is correct
22 Correct 10 ms 14468 KB Output is correct
23 Correct 6 ms 14172 KB Output is correct
24 Correct 7 ms 14388 KB Output is correct
25 Correct 13 ms 14424 KB Output is correct
26 Correct 5 ms 14392 KB Output is correct
27 Correct 8 ms 14432 KB Output is correct
28 Correct 6 ms 14168 KB Output is correct

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14172 KB Output is correct
2 Correct 2 ms 14172 KB Output is correct
3 Correct 4 ms 14428 KB Output is correct
4 Correct 5 ms 12424 KB Output is correct
5 Correct 4 ms 14168 KB Output is correct
6 Correct 4 ms 14172 KB Output is correct
7 Correct 4 ms 14172 KB Output is correct
8 Correct 3 ms 14172 KB Output is correct
9 Correct 3 ms 14168 KB Output is correct
10 Correct 3 ms 14384 KB Output is correct
11 Correct 3 ms 14168 KB Output is correct
12 Correct 2 ms 14168 KB Output is correct
13 Correct 3 ms 14336 KB Output is correct
14 Correct 3 ms 14172 KB Output is correct
15 Correct 2 ms 14172 KB Output is correct
16 Correct 12 ms 14428 KB Output is correct
17 Correct 5 ms 14428 KB Output is correct
18 Correct 10 ms 14428 KB Output is correct
19 Correct 2 ms 14172 KB Output is correct
20 Correct 9 ms 14428 KB Output is correct
21 Correct 7 ms 14428 KB Output is correct
22 Correct 10 ms 14468 KB Output is correct
23 Correct 6 ms 14172 KB Output is correct
24 Correct 7 ms 14388 KB Output is correct
25 Correct 13 ms 14424 KB Output is correct
26 Correct 5 ms 14392 KB Output is correct
27 Correct 8 ms 14432 KB Output is correct
28 Correct 6 ms 14168 KB Output is correct
29 Execution timed out 5028 ms 13660 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14172 KB Output is correct
2 Correct 2 ms 14172 KB Output is correct
3 Correct 4 ms 14428 KB Output is correct
4 Correct 5 ms 12424 KB Output is correct
5 Correct 4 ms 14168 KB Output is correct
6 Correct 4 ms 14172 KB Output is correct
7 Correct 4 ms 14172 KB Output is correct
8 Correct 3 ms 14172 KB Output is correct
9 Correct 3 ms 14168 KB Output is correct
10 Correct 3 ms 14384 KB Output is correct
11 Correct 3 ms 14168 KB Output is correct
12 Correct 2 ms 14168 KB Output is correct
13 Correct 3 ms 14336 KB Output is correct
14 Correct 3 ms 14172 KB Output is correct
15 Correct 2 ms 14172 KB Output is correct
16 Correct 12 ms 14428 KB Output is correct
17 Correct 5 ms 14428 KB Output is correct
18 Correct 10 ms 14428 KB Output is correct
19 Correct 2 ms 14172 KB Output is correct
20 Correct 9 ms 14428 KB Output is correct
21 Correct 7 ms 14428 KB Output is correct
22 Correct 10 ms 14468 KB Output is correct
23 Correct 6 ms 14172 KB Output is correct
24 Correct 7 ms 14388 KB Output is correct
25 Correct 13 ms 14424 KB Output is correct
26 Correct 5 ms 14392 KB Output is correct
27 Correct 8 ms 14432 KB Output is correct
28 Correct 6 ms 14168 KB Output is correct
29 Execution timed out 5028 ms 13660 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14172 KB Output is correct
2 Correct 3 ms 14172 KB Output is correct
3 Correct 3 ms 14168 KB Output is correct
4 Correct 4 ms 14172 KB Output is correct
5 Execution timed out 5096 ms 14468 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14168 KB Output is correct
2 Correct 3 ms 14172 KB Output is correct
3 Correct 3 ms 14172 KB Output is correct
4 Correct 9 ms 14172 KB Output is correct
5 Correct 18 ms 14172 KB Output is correct
6 Correct 3 ms 14428 KB Output is correct
7 Correct 9 ms 14428 KB Output is correct
8 Execution timed out 5098 ms 14428 KB Time limit exceeded
9 Halted 0 ms 0 KB -