oj.uz

Submission #876856

# Submission time Handle Problem Language Result Execution time Memory
876856 2023-11-22T12:39:28 Z vivkostov Jail (JOI22_jail) C++14
61 / 100
 5000 ms 165972 KB 
#include<bits/stdc++.h>
#define endl "\n"
using namespace std;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
int q,n,m,c,d,a[200005],b[200005],tip[200005],up[200005],lev[200005],bin[200005][60],whos[200005],whof[200005],marked[505][505],usedc[200005];
vector<int>v[200005],mod[200005];
void dfs(int beg,int last,int level,int p)
{
    lev[beg]=level;
    bin[beg][0]=p;
    if(tip[beg])
    {
        up[beg]=last;
        last=beg;
    }
    int w;
    for(int i=0;i<v[beg].size();i++)
    {
        w=v[beg][i];
        if(!lev[w])dfs(w,last,level+1,beg);
    }
}
void make_bin()
{
    for(int j=1;j<=30;j++)
    {
        for(int i=1;i<=n;i++)
        {
            bin[i][j]=bin[bin[i][j-1]][j-1];
        }
    }
}
int lca(int a,int b)
{
    if(lev[a]>lev[b])swap(a,b);
    for(int i=29;i>=0;i--)
    {
        if(lev[a]<=lev[bin[b][i]])b=bin[b][i];
    }
    if(a==b)return a;
    for(int i=29;i>=0;i--)
    {
        if(bin[a][i]!=bin[b][i])
        {
            a=bin[a][i];
            b=bin[b][i];
        }
    }
    return bin[a][0];
}
void make_graph(int g)
{
    if(tip[a[g]]==3)
    {
        mod[whos[a[g]]].push_back(g);
        marked[whos[a[g]]][g]=1;
        mod[g].push_back(whof[a[g]]);
        marked[g][whof[a[g]]]=1;
    }
    if(tip[b[g]]==3)
    {
        mod[whos[b[g]]].push_back(g);
        marked[whos[b[g]]][g]=1;
        mod[g].push_back(whof[b[g]]);
        marked[g][whof[b[g]]]=1;
    }
    int l=lev[lca(a[g],b[g])],seg=up[a[g]];
    while(lev[seg]>=l)
    {
        if((tip[seg]==1||tip[seg]==3)&&!marked[whos[seg]][g])
        {
            mod[whos[seg]].push_back(g);
            marked[whos[seg]][g]=1;
        }
        if((tip[seg]==2||tip[seg]==3)&&!marked[g][whof[seg]])
        {
            mod[g].push_back(whof[seg]);
            marked[g][whof[seg]]=1;
        }
        seg=up[seg];
    }
    seg=up[b[g]];
    while(lev[seg]>=l)
    {
        if((tip[seg]==1||tip[seg]==3)&&!marked[whos[seg]][g])
        {
            mod[whos[seg]].push_back(g);
            marked[whos[seg]][g]=1;
        }
        if((tip[seg]==2||tip[seg]==3)&&!marked[g][whof[seg]])
        {
            mod[g].push_back(whof[seg]);
            marked[g][whof[seg]]=1;
        }
        seg=up[seg];
    }
}
int lamp;
void cycle(int beg)
{
    int w;
    usedc[beg]=1;
    for(long unsigned int i=0;i<mod[beg].size();i++)
    {
        w=mod[beg][i];
        if(!usedc[w])cycle(w);
        if(usedc[w]==1&&w!=beg)lamp=1;
    }
    usedc[beg]=2;
}
void resh()
{
    dfs(1,0,1,0);
    make_bin();
    for(int i=1;i<=m;i++)make_graph(i);
    /*for(int i=1;i<=m;i++)
    {
        cout<<i<<" | ";
        for(int j=0;j<mod[i].size();j++)
        {
            cout<<mod[i][j]<<" ";
        }
        cout<<endl;
    }
    */
    for(int i=1;i<=m;i++)
    {
        if(!usedc[i])cycle(i);
    }
    if(lamp)cout<<"No"<<endl;
    else cout<<"Yes"<<endl;
    for(int i=0;i<=n;i++)
    {
        a[i]=0;
        b[i]=0;
        tip[i]=0;
        up[i]=0;
        lev[i]=0;
        for(int j=0;j<=40;j++)bin[i][j]=0;
        whos[i]=0;
        whof[i]=0;
        usedc[i]=0;
        v[i].clear();
        mod[i].clear();
    }
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=m;j++)
        {
            marked[i][j]=0;
        }
    }
    lamp=0;
}
void read()
{
    cin>>q;
    for(int z=1;z<=q;z++)
    {
        cin>>n;
        for(int i=1;i<n;i++)
        {
            cin>>c>>d;
            v[c].push_back(d);
            v[d].push_back(c);
        }
        cin>>m;
        for(int i=1;i<=m;i++)
        {
            cin>>a[i]>>b[i];
            whos[a[i]]=i;
            whof[b[i]]=i;
            if(tip[a[i]])tip[a[i]]=3;
            else tip[a[i]]=1;
            if(tip[b[i]])tip[b[i]]=3;
            else tip[b[i]]=2;
        }
        resh();
    }
}
int main()
{
    speed();
    read();
    return 0;
}

Compilation message

jail.cpp: In function 'void dfs(int, int, int, int)':
jail.cpp:22:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for(int i=0;i<v[beg].size();i++)
      |                 ~^~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14940 KB Output is correct
2 Correct 3 ms 14940 KB Output is correct
3 Correct 3 ms 14940 KB Output is correct
4 Correct 12 ms 15040 KB Output is correct
5 Correct 25 ms 15036 KB Output is correct
6 Correct 3 ms 14936 KB Output is correct
7 Correct 3 ms 15056 KB Output is correct
8 Correct 5 ms 14940 KB Output is correct
9 Correct 40 ms 16724 KB Output is correct
10 Correct 51 ms 57692 KB Output is correct
11 Correct 8 ms 14936 KB Output is correct
12 Correct 41 ms 14940 KB Output is correct
13 Runtime error 152 ms 165972 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14936 KB Output is correct
2 Correct 2 ms 14940 KB Output is correct
3 Correct 3 ms 14940 KB Output is correct
4 Correct 3 ms 14940 KB Output is correct
5 Correct 4 ms 14940 KB Output is correct
6 Correct 4 ms 14940 KB Output is correct
7 Correct 4 ms 14940 KB Output is correct
8 Correct 3 ms 14940 KB Output is correct
9 Correct 4 ms 14936 KB Output is correct
10 Correct 3 ms 15004 KB Output is correct
11 Correct 3 ms 15076 KB Output is correct
12 Correct 3 ms 14940 KB Output is correct
13 Correct 4 ms 14940 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14936 KB Output is correct
2 Correct 2 ms 14940 KB Output is correct
3 Correct 3 ms 14940 KB Output is correct
4 Correct 3 ms 14940 KB Output is correct
5 Correct 4 ms 14940 KB Output is correct
6 Correct 4 ms 14940 KB Output is correct
7 Correct 4 ms 14940 KB Output is correct
8 Correct 3 ms 14940 KB Output is correct
9 Correct 4 ms 14936 KB Output is correct
10 Correct 3 ms 15004 KB Output is correct
11 Correct 3 ms 15076 KB Output is correct
12 Correct 3 ms 14940 KB Output is correct
13 Correct 4 ms 14940 KB Output is correct
14 Correct 3 ms 14956 KB Output is correct
15 Correct 3 ms 14940 KB Output is correct
16 Correct 3 ms 14940 KB Output is correct
17 Correct 3 ms 14940 KB Output is correct
18 Correct 4 ms 15004 KB Output is correct
19 Correct 3 ms 14940 KB Output is correct
20 Correct 4 ms 15012 KB Output is correct
21 Correct 4 ms 15084 KB Output is correct
22 Correct 4 ms 14940 KB Output is correct
23 Correct 3 ms 14940 KB Output is correct
24 Correct 3 ms 14940 KB Output is correct
25 Correct 4 ms 14940 KB Output is correct
26 Correct 3 ms 15024 KB Output is correct
27 Correct 4 ms 15072 KB Output is correct
28 Correct 3 ms 14940 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14936 KB Output is correct
2 Correct 2 ms 14940 KB Output is correct
3 Correct 3 ms 14940 KB Output is correct
4 Correct 3 ms 14940 KB Output is correct
5 Correct 4 ms 14940 KB Output is correct
6 Correct 4 ms 14940 KB Output is correct
7 Correct 4 ms 14940 KB Output is correct
8 Correct 3 ms 14940 KB Output is correct
9 Correct 4 ms 14936 KB Output is correct
10 Correct 3 ms 15004 KB Output is correct
11 Correct 3 ms 15076 KB Output is correct
12 Correct 3 ms 14940 KB Output is correct
13 Correct 4 ms 14940 KB Output is correct
14 Correct 3 ms 14956 KB Output is correct
15 Correct 3 ms 14940 KB Output is correct
16 Correct 3 ms 14940 KB Output is correct
17 Correct 3 ms 14940 KB Output is correct
18 Correct 4 ms 15004 KB Output is correct
19 Correct 3 ms 14940 KB Output is correct
20 Correct 4 ms 15012 KB Output is correct
21 Correct 4 ms 15084 KB Output is correct
22 Correct 4 ms 14940 KB Output is correct
23 Correct 3 ms 14940 KB Output is correct
24 Correct 3 ms 14940 KB Output is correct
25 Correct 4 ms 14940 KB Output is correct
26 Correct 3 ms 15024 KB Output is correct
27 Correct 4 ms 15072 KB Output is correct
28 Correct 3 ms 14940 KB Output is correct
29 Correct 5 ms 14940 KB Output is correct
30 Correct 5 ms 15008 KB Output is correct
31 Correct 4 ms 15112 KB Output is correct
32 Correct 4 ms 14940 KB Output is correct
33 Correct 4 ms 14940 KB Output is correct
34 Correct 5 ms 14936 KB Output is correct
35 Correct 5 ms 14940 KB Output is correct
36 Correct 4 ms 15004 KB Output is correct
37 Correct 4 ms 14940 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14936 KB Output is correct
2 Correct 2 ms 14940 KB Output is correct
3 Correct 3 ms 14940 KB Output is correct
4 Correct 3 ms 14940 KB Output is correct
5 Correct 4 ms 14940 KB Output is correct
6 Correct 4 ms 14940 KB Output is correct
7 Correct 4 ms 14940 KB Output is correct
8 Correct 3 ms 14940 KB Output is correct
9 Correct 4 ms 14936 KB Output is correct
10 Correct 3 ms 15004 KB Output is correct
11 Correct 3 ms 15076 KB Output is correct
12 Correct 3 ms 14940 KB Output is correct
13 Correct 4 ms 14940 KB Output is correct
14 Correct 3 ms 14956 KB Output is correct
15 Correct 3 ms 14940 KB Output is correct
16 Correct 3 ms 14940 KB Output is correct
17 Correct 3 ms 14940 KB Output is correct
18 Correct 4 ms 15004 KB Output is correct
19 Correct 3 ms 14940 KB Output is correct
20 Correct 4 ms 15012 KB Output is correct
21 Correct 4 ms 15084 KB Output is correct
22 Correct 4 ms 14940 KB Output is correct
23 Correct 3 ms 14940 KB Output is correct
24 Correct 3 ms 14940 KB Output is correct
25 Correct 4 ms 14940 KB Output is correct
26 Correct 3 ms 15024 KB Output is correct
27 Correct 4 ms 15072 KB Output is correct
28 Correct 3 ms 14940 KB Output is correct
29 Correct 5 ms 14940 KB Output is correct
30 Correct 5 ms 15008 KB Output is correct
31 Correct 4 ms 15112 KB Output is correct
32 Correct 4 ms 14940 KB Output is correct
33 Correct 4 ms 14940 KB Output is correct
34 Correct 5 ms 14936 KB Output is correct
35 Correct 5 ms 14940 KB Output is correct
36 Correct 4 ms 15004 KB Output is correct
37 Correct 4 ms 14940 KB Output is correct
38 Correct 40 ms 17492 KB Output is correct
39 Correct 60 ms 58716 KB Output is correct
40 Correct 43 ms 17372 KB Output is correct
41 Correct 29 ms 15964 KB Output is correct
42 Correct 33 ms 17496 KB Output is correct
43 Correct 24 ms 16220 KB Output is correct
44 Correct 12 ms 15420 KB Output is correct
45 Correct 59 ms 48728 KB Output is correct
46 Correct 57 ms 48860 KB Output is correct
47 Correct 47 ms 53436 KB Output is correct
48 Correct 48 ms 53388 KB Output is correct
49 Correct 60 ms 49128 KB Output is correct
50 Correct 52 ms 48868 KB Output is correct
51 Correct 46 ms 50256 KB Output is correct
52 Correct 48 ms 50260 KB Output is correct
53 Correct 13 ms 17752 KB Output is correct
54 Correct 59 ms 48720 KB Output is correct

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14940 KB Output is correct
2 Correct 2 ms 14940 KB Output is correct
3 Correct 2 ms 14940 KB Output is correct
4 Correct 2 ms 14940 KB Output is correct
5 Correct 8 ms 14940 KB Output is correct
6 Correct 5 ms 14936 KB Output is correct
7 Correct 3 ms 14940 KB Output is correct
8 Correct 3 ms 14940 KB Output is correct
9 Correct 3 ms 15192 KB Output is correct
10 Correct 3 ms 14940 KB Output is correct
11 Correct 3 ms 14940 KB Output is correct
12 Correct 4 ms 14940 KB Output is correct
13 Correct 24 ms 15452 KB Output is correct
14 Correct 30 ms 15816 KB Output is correct
15 Correct 27 ms 15448 KB Output is correct
16 Execution timed out 5015 ms 48144 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14940 KB Output is correct
2 Correct 3 ms 14940 KB Output is correct
3 Correct 3 ms 14940 KB Output is correct
4 Correct 12 ms 15040 KB Output is correct
5 Correct 25 ms 15036 KB Output is correct
6 Correct 3 ms 14936 KB Output is correct
7 Correct 3 ms 15056 KB Output is correct
8 Correct 5 ms 14940 KB Output is correct
9 Correct 40 ms 16724 KB Output is correct
10 Correct 51 ms 57692 KB Output is correct
11 Correct 8 ms 14936 KB Output is correct
12 Correct 41 ms 14940 KB Output is correct
13 Runtime error 152 ms 165972 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -