oj.uz

Submission #712926

# Submission time Handle Problem Language Result Execution time Memory
712926 2023-03-20T13:26:33 Z lam Jail (JOI22_jail) C++14
21 / 100
 5000 ms 3320 KB 
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 2e4 + 10;
typedef pair<int,int> ii;
#define ff first
#define ss second
int n,m;
vector <int> adj[maxn];
int par[18][maxn];
int in[maxn],out[maxn],cnt;
bool dau[maxn];
vector <int> d;
ii num[maxn], a[maxn];
void dfs(int x, int p)
{
    par[0][x]=p;
    in[x]=++cnt;
    for (int i=1; i<=17; i++) par[i][x]=par[i-1][par[i-1][x]];
    for (int i:adj[x])
        if (i!=p)
            dfs(i,x);
    out[x]=cnt;
}
bool check(int u, int v)
{
    return in[u]<=in[v]&&out[v]<=out[u];
}
int lca(int u, int v)
{
    if (check(u,v)) return u;
    if (check(v,u)) return v;
    for (int i=17; i>=0; i--)
        if (!check(par[i][u],v)) u=par[i][u];
    return par[0][u];
}
void upd(int u, int v, int type)
{
//    int it=1;
    while (v!=u)
    {
//        it++; if (it==10) break;
//        cerr<<u<<' '<<v<<endl;
        if (type==1) num[v].ff++;
        else num[v].ss++;
        v=par[0][v];
    }
}
bool check_mid(int u, int v, int mid)
{
    return check(u,mid)&&check(mid,v);
}
bool check_path(int u, int v, int x, int y)
{
    /**
    u x y v
    **/
    int p=lca(u,v);
    if ((check_mid(p,u,x)||check_mid(p,v,x))&&(check_mid(p,u,y)||check_mid(p,v,y))) return 1;
    return 0;
}
void xuly()
{
    cin>>n;
    for (int i=1; i<=n; i++) adj[i].clear(), in[i]=out[i]=0, num[i]={0,0}; cnt=0;
    for (int i=1; i<n; i++)
    {
        int u,v; cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1,1);
    cin>>m; d.clear();
    for (int i=1; i<=m; i++) cin>>a[i].ff>>a[i].ss, d.push_back(i);
    do
    {
        fill_n(dau,n+1,0);
        for (int i=1; i<=m; i++) dau[a[i].ff] = 1;
//        for (int i:d) cout<<i<<' '; cout<<'\n';
        bool ccheck = 1;
        for (int i:d)
        {
            int u = a[i].ff; int v=a[i].ss;
            dau[u] = 0;
//            for (int j=1; j<=n; j++) cout<<dau[j]<<' '; cout<<"!!\n";
            int p=lca(u,v);
            while (u!=p)
            {
                if (dau[u]) ccheck = 0;
                u=par[0][u];
            }
            if (dau[p])  ccheck=0;
            while (v!=p)
            {
                if (dau[v]) ccheck=0;
                v=par[0][v];
            }
            dau[a[i].ss] = 1;
            if (!ccheck) break;
        }
        if (!ccheck) continue;
        cout<<"Yes\n";
        return;
    }
    while (next_permutation(d.begin(),d.end()));
    cout<<"No\n";
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    int tt; cin>>tt;
    while (tt--) xuly();
}

Compilation message

jail.cpp: In function 'void xuly()':
jail.cpp:64:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   64 |     for (int i=1; i<=n; i++) adj[i].clear(), in[i]=out[i]=0, num[i]={0,0}; cnt=0;
      |     ^~~
jail.cpp:64:76: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   64 |     for (int i=1; i<=n; i++) adj[i].clear(), in[i]=out[i]=0, num[i]={0,0}; cnt=0;
      |                                                                            ^~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3156 KB Output is correct
2 Correct 2 ms 3156 KB Output is correct
3 Correct 2 ms 3156 KB Output is correct
4 Correct 10 ms 3264 KB Output is correct
5 Correct 21 ms 3316 KB Output is correct
6 Correct 2 ms 3284 KB Output is correct
7 Correct 6 ms 3284 KB Output is correct
8 Execution timed out 5091 ms 3156 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3156 KB Output is correct
2 Correct 2 ms 3156 KB Output is correct
3 Correct 3 ms 3284 KB Output is correct
4 Correct 3 ms 3284 KB Output is correct
5 Correct 3 ms 3284 KB Output is correct
6 Correct 3 ms 3288 KB Output is correct
7 Correct 3 ms 3284 KB Output is correct
8 Correct 3 ms 3284 KB Output is correct
9 Correct 3 ms 3260 KB Output is correct
10 Correct 3 ms 3320 KB Output is correct
11 Correct 3 ms 3284 KB Output is correct
12 Correct 2 ms 3284 KB Output is correct
13 Correct 2 ms 3300 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3156 KB Output is correct
2 Correct 2 ms 3156 KB Output is correct
3 Correct 3 ms 3284 KB Output is correct
4 Correct 3 ms 3284 KB Output is correct
5 Correct 3 ms 3284 KB Output is correct
6 Correct 3 ms 3288 KB Output is correct
7 Correct 3 ms 3284 KB Output is correct
8 Correct 3 ms 3284 KB Output is correct
9 Correct 3 ms 3260 KB Output is correct
10 Correct 3 ms 3320 KB Output is correct
11 Correct 3 ms 3284 KB Output is correct
12 Correct 2 ms 3284 KB Output is correct
13 Correct 2 ms 3300 KB Output is correct
14 Correct 2 ms 3156 KB Output is correct
15 Correct 2 ms 3156 KB Output is correct
16 Correct 7 ms 3288 KB Output is correct
17 Correct 3 ms 3284 KB Output is correct
18 Correct 6 ms 3284 KB Output is correct
19 Correct 2 ms 3156 KB Output is correct
20 Correct 4 ms 3284 KB Output is correct
21 Correct 5 ms 3284 KB Output is correct
22 Correct 5 ms 3292 KB Output is correct
23 Correct 3 ms 3156 KB Output is correct
24 Correct 3 ms 3156 KB Output is correct
25 Correct 12 ms 3288 KB Output is correct
26 Correct 4 ms 3284 KB Output is correct
27 Correct 4 ms 3284 KB Output is correct
28 Correct 8 ms 3156 KB Output is correct

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3156 KB Output is correct
2 Correct 2 ms 3156 KB Output is correct
3 Correct 3 ms 3284 KB Output is correct
4 Correct 3 ms 3284 KB Output is correct
5 Correct 3 ms 3284 KB Output is correct
6 Correct 3 ms 3288 KB Output is correct
7 Correct 3 ms 3284 KB Output is correct
8 Correct 3 ms 3284 KB Output is correct
9 Correct 3 ms 3260 KB Output is correct
10 Correct 3 ms 3320 KB Output is correct
11 Correct 3 ms 3284 KB Output is correct
12 Correct 2 ms 3284 KB Output is correct
13 Correct 2 ms 3300 KB Output is correct
14 Correct 2 ms 3156 KB Output is correct
15 Correct 2 ms 3156 KB Output is correct
16 Correct 7 ms 3288 KB Output is correct
17 Correct 3 ms 3284 KB Output is correct
18 Correct 6 ms 3284 KB Output is correct
19 Correct 2 ms 3156 KB Output is correct
20 Correct 4 ms 3284 KB Output is correct
21 Correct 5 ms 3284 KB Output is correct
22 Correct 5 ms 3292 KB Output is correct
23 Correct 3 ms 3156 KB Output is correct
24 Correct 3 ms 3156 KB Output is correct
25 Correct 12 ms 3288 KB Output is correct
26 Correct 4 ms 3284 KB Output is correct
27 Correct 4 ms 3284 KB Output is correct
28 Correct 8 ms 3156 KB Output is correct
29 Execution timed out 5029 ms 3284 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3156 KB Output is correct
2 Correct 2 ms 3156 KB Output is correct
3 Correct 3 ms 3284 KB Output is correct
4 Correct 3 ms 3284 KB Output is correct
5 Correct 3 ms 3284 KB Output is correct
6 Correct 3 ms 3288 KB Output is correct
7 Correct 3 ms 3284 KB Output is correct
8 Correct 3 ms 3284 KB Output is correct
9 Correct 3 ms 3260 KB Output is correct
10 Correct 3 ms 3320 KB Output is correct
11 Correct 3 ms 3284 KB Output is correct
12 Correct 2 ms 3284 KB Output is correct
13 Correct 2 ms 3300 KB Output is correct
14 Correct 2 ms 3156 KB Output is correct
15 Correct 2 ms 3156 KB Output is correct
16 Correct 7 ms 3288 KB Output is correct
17 Correct 3 ms 3284 KB Output is correct
18 Correct 6 ms 3284 KB Output is correct
19 Correct 2 ms 3156 KB Output is correct
20 Correct 4 ms 3284 KB Output is correct
21 Correct 5 ms 3284 KB Output is correct
22 Correct 5 ms 3292 KB Output is correct
23 Correct 3 ms 3156 KB Output is correct
24 Correct 3 ms 3156 KB Output is correct
25 Correct 12 ms 3288 KB Output is correct
26 Correct 4 ms 3284 KB Output is correct
27 Correct 4 ms 3284 KB Output is correct
28 Correct 8 ms 3156 KB Output is correct
29 Execution timed out 5029 ms 3284 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3156 KB Output is correct
2 Correct 2 ms 3156 KB Output is correct
3 Correct 2 ms 3156 KB Output is correct
4 Correct 2 ms 3156 KB Output is correct
5 Execution timed out 5073 ms 3228 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3156 KB Output is correct
2 Correct 2 ms 3156 KB Output is correct
3 Correct 2 ms 3156 KB Output is correct
4 Correct 10 ms 3264 KB Output is correct
5 Correct 21 ms 3316 KB Output is correct
6 Correct 2 ms 3284 KB Output is correct
7 Correct 6 ms 3284 KB Output is correct
8 Execution timed out 5091 ms 3156 KB Time limit exceeded
9 Halted 0 ms 0 KB -