oj.uz

Submission #876804

# Submission time Handle Problem Language Result Execution time Memory
876804 2023-11-22T11:12:41 Z vivkostov Jail (JOI22_jail) C++14
0 / 100
 5000 ms 165948 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;
    int w;
    if(tip[beg])
    {
        up[beg]=last;
        last=beg;
    }
    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 i=1;i<=n;i++)
    {
        int j=1;
        while(bin[bin[i][j-1]][j-1]!=0&&j<1000)
        {
            bin[i][j]=bin[bin[i][j-1]][j-1];
            j++;
        }
    }
}
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]];
    int h=0;
    while(lev[seg]>=l&&h<1000)
    {
        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&&h<1000)
    {
        h++;
        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 par)
{
    int w;
    usedc[beg]=1;
    for(int i=0;i<mod[beg].size();i++)
    {
        w=mod[beg][i];
        if(!usedc[w])cycle(w,beg);
        if(usedc[w]==1&&w!=beg)
        {
            lamp=1;
            return;
        }
    }
    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,0);
    }
    if(lamp)cout<<"No"<<endl;
    else cout<<"Yes"<<endl;
    for(int i=1;i<=n;i++)
    {
        a[i]=0;
        b[i]=0;
        tip[i]=0;
        up[i]=0;
        lev[i]=0;
        for(int j=0;j<=29;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++)
      |                 ~^~~~~~~~~~~~~~
jail.cpp: In function 'void cycle(int, int)':
jail.cpp:112:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |     for(int i=0;i<mod[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 14952 KB Output is correct
3 Correct 3 ms 14940 KB Output is correct
4 Correct 10 ms 15044 KB Output is correct
5 Correct 17 ms 14940 KB Output is correct
6 Correct 4 ms 15056 KB Output is correct
7 Correct 5 ms 15192 KB Output is correct
8 Correct 4 ms 14940 KB Output is correct
9 Correct 34 ms 16888 KB Output is correct
10 Correct 51 ms 57748 KB Output is correct
11 Correct 7 ms 14940 KB Output is correct
12 Correct 34 ms 15040 KB Output is correct
13 Runtime error 146 ms 165948 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14936 KB Output is correct
2 Correct 3 ms 14940 KB Output is correct
3 Correct 3 ms 14960 KB Output is correct
4 Execution timed out 5026 ms 14936 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14936 KB Output is correct
2 Correct 3 ms 14940 KB Output is correct
3 Correct 3 ms 14960 KB Output is correct
4 Execution timed out 5026 ms 14936 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14936 KB Output is correct
2 Correct 3 ms 14940 KB Output is correct
3 Correct 3 ms 14960 KB Output is correct
4 Execution timed out 5026 ms 14936 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14936 KB Output is correct
2 Correct 3 ms 14940 KB Output is correct
3 Correct 3 ms 14960 KB Output is correct
4 Execution timed out 5026 ms 14936 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14936 KB Output is correct
2 Correct 3 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 8 ms 15020 KB Output is correct
6 Correct 3 ms 14940 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 14940 KB Output is correct
10 Execution timed out 5053 ms 14940 KB Time limit exceeded
11 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 14952 KB Output is correct
3 Correct 3 ms 14940 KB Output is correct
4 Correct 10 ms 15044 KB Output is correct
5 Correct 17 ms 14940 KB Output is correct
6 Correct 4 ms 15056 KB Output is correct
7 Correct 5 ms 15192 KB Output is correct
8 Correct 4 ms 14940 KB Output is correct
9 Correct 34 ms 16888 KB Output is correct
10 Correct 51 ms 57748 KB Output is correct
11 Correct 7 ms 14940 KB Output is correct
12 Correct 34 ms 15040 KB Output is correct
13 Runtime error 146 ms 165948 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -