oj.uz

Submission #927410

# Submission time Handle Problem Language Result Execution time Memory
927410 2024-02-14T20:14:39 Z andrei_boaca Jail (JOI22_jail) C++17
26 / 100
 3423 ms 154328 KB 
#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> pii;
int t,n,m,A[120005],B[120005],in[120005],out[120005],timp,par[120005],niv[120005],dp[21][120005],nr[120005];
bool isheavy[120005];
vector<int> muchii[120005];
vector<vector<int>> v;
vector<set<pii>> suf,active;
set<pii> vtm;
vector<vector<set<int>>> arb;
vector<int> tati;
vector<set<int>> emp;
int where[120005],poz[120005];
vector<int> stiva;
bool use[120005];
bool isancestor(int a,int b)
{
    return in[a]<=in[b]&&out[a]>=out[b];
}
int LCA(int a,int b)
{
    if(niv[a]>niv[b])
        swap(a,b);
    if(isancestor(a,b))
        return a;
    for(int i=18;i>=0;i--)
        if(dp[i][a]!=0&&!isancestor(dp[i][a],b))
            a=dp[i][a];
    return par[a];
}
int dist(int a,int b)
{
    int lca=LCA(a,b);
    return niv[a]+niv[b]-2*niv[lca];
}
void initdfs(int nod)
{
    nr[nod]=1;
    timp++;
    in[nod]=timp;
    dp[0][nod]=par[nod];
    for(int i=1;i<=18;i++)
        dp[i][nod]=dp[i-1][dp[i-1][nod]];
    int who=0,maxim=0;
    for(int i:muchii[nod])
        if(i!=par[nod])
        {
            par[i]=nod;
            niv[i]=niv[nod]+1;
            initdfs(i);
            nr[nod]+=nr[i];
            if(nr[i]>maxim)
            {
                maxim=nr[i];
                who=i;
            }
        }
    if(who!=0)
        isheavy[who]=1;
    out[nod]=timp;
}
void buildhld()
{
    for(int i=1;i<=n;i++)
    {
        bool ok=1;
        for(int j:muchii[i])
            if(j!=par[i]&&isheavy[j])
            {
                ok=0;
                break;
            }
        if(ok)
        {
            vector<int> nodes;
            int nod=i;
            while(true)
            {
                nodes.push_back(nod);
                if(!isheavy[nod])
                    break;
                nod=par[nod];
            }
            for(int i=0;i<nodes.size();i++)
            {
                where[nodes[i]]=v.size();
                poz[nodes[i]]=i;
            }
            v.push_back(nodes);
            arb.push_back(emp);
            suf.push_back(vtm);
            active.push_back(vtm);
            int lg=arb.size();
            lg--;
            arb[lg].resize(5*(int)nodes.size()+5);
        }
    }
}
void addnode(int nod,int ind,int add)
{
    int chain=where[nod];
    int p=poz[nod];
    if(add==1)
        active[chain].insert({p,ind});
    else if(active[chain].find({p,ind})!=active[chain].end())
        active[chain].erase({p,ind});
    else
        assert(false);
}
void update(int chain,int nod,int st,int dr,int a,int b,int val,int add)
{
    assert(nod<arb[chain].size());
    if(st>=a&&dr<=b)
    {
        if(add==1)
            arb[chain][nod].insert(val);
        else if(arb[chain][nod].find(val)!=arb[chain][nod].end())
            arb[chain][nod].erase(val);
        else
            assert(false);
        return;
    }
    int mij=(st+dr)/2;
    if(a<=mij)
        update(chain,nod*2,st,mij,a,b,val,add);
    if(b>mij)
        update(chain,nod*2+1,mij+1,dr,a,b,val,add);
}
void query(int chain,int nod,int st,int dr,int p)
{
    assert(nod<arb[chain].size());
    tati.push_back(nod);
    if(st==dr)
        return;
    int mij=(st+dr)/2;
    if(p<=mij)
        query(chain,nod*2,st,mij,p);
    if(p>mij)
        query(chain,nod*2+1,mij+1,dr,p);
}
void addseg(int a,int b,int ind,int add)
{
    int lca=LCA(a,b);
    while(niv[a]>=niv[lca])
    {
        int p=poz[a];
        int chain=where[a];
        int last=v[chain].size();
        last--;
        if(where[a]==where[lca])
            last=poz[lca];
        if(p<=last)
        {
            if(last!=(int)v[chain].size()-1)
                update(chain,1,0,(int)v[chain].size()-1,p,last,ind,add);
            else
            {
                pii x={p,ind};
                if(add==1)
                    suf[chain].insert(x);
                else if(suf[chain].find(x)!=suf[chain].end())
                    suf[chain].erase(x);
                else
                    assert(false);
            }
        }
        a=par[v[chain][last]];
    }

    while(niv[b]>niv[lca])
    {
        int p=poz[b];
        int chain=where[b];
        int last=v[chain].size();
        last--;
        if(where[b]==where[lca])
            last=poz[lca]-1;
        if(p<=last)
        {
            if(last!=(int)v[chain].size()-1)
                update(chain,1,0,(int)v[chain].size()-1,p,last,ind,add);
            else
            {
                pii x={p,ind};
                if(add==1)
                    suf[chain].insert(x);
                else if(suf[chain].find(x)!=suf[chain].end())
                    suf[chain].erase(x);
                else
                    assert(false);
            }
        }
        b=par[v[chain][last]];
    }
}
void dfs1(int nod)
{
    use[nod]=1;
    addseg(A[nod],B[nod],nod,-1);
    addnode(A[nod],nod,-1);
    int chain=where[B[nod]];
    int p=poz[B[nod]];
    while(!suf[chain].empty())
    {
        auto it=suf[chain].upper_bound({p,1e9});
        if(it==suf[chain].begin())
            break;
        it=prev(it);
        int x=(*it).second;
        dfs1(x);
    }
    tati.clear();
    query(chain,1,0,v[chain].size()-1,p);
    for(int x:tati)
    {
        while(!arb[chain][x].empty())
        {
            int y=*arb[chain][x].begin();
            dfs1(y);
        }
    }
    int a=A[nod];
    int b=B[nod];
    int lca=LCA(a,b);
    while(a!=0&&niv[a]>=niv[lca])
    {
        p=poz[a];
        chain=where[a];
        int last=v[chain].size();
        last--;
        if(where[a]==where[lca])
            last=poz[lca];
        while(!active[chain].empty())
        {
            auto it=active[chain].lower_bound({p,0});
            if(it==active[chain].end())
                break;
            if((*it).first>last)
                break;
            int x=(*it).second;
            dfs1(x);
        }
        a=par[v[chain][last]];
    }
    while(b!=0&&niv[b]>niv[lca])
    {
        p=poz[b];
        chain=where[b];
        int last=v[chain].size();
        last--;
        if(where[b]==where[lca])
            last=poz[lca]-1;
        while(!active[chain].empty())
        {
            auto it=active[chain].lower_bound({p,0});
            if(it==active[chain].end())
                break;
            if((*it).first>last)
                break;
            int x=(*it).second;
            dfs1(x);
        }
        b=par[v[chain][last]];
    }
    stiva.push_back(nod);
}
void dfs2(int nod)
{
    use[nod]=1;
    addseg(A[nod],B[nod],nod,-1);
    addnode(B[nod],nod,-1);
    int chain=where[A[nod]];
    int p=poz[A[nod]];
    while(!suf[chain].empty())
    {
        auto it=suf[chain].upper_bound({p,1e9});
        if(it==suf[chain].begin())
            break;
        it=prev(it);
        int x=(*it).second;
        dfs2(x);
    }
    tati.clear();
    query(chain,1,0,v[chain].size()-1,p);
    for(int x:tati)
    {
        while(!arb[chain][x].empty())
        {
            int y=*arb[chain][x].begin();
            dfs2(y);
        }
    }
    int a=A[nod];
    int b=B[nod];
    int lca=LCA(a,b);
    while(a!=0&&niv[a]>=niv[lca])
    {
        p=poz[a];
        chain=where[a];
        int last=v[chain].size();
        last--;
        if(where[a]==where[lca])
            last=poz[lca];
        while(!active[chain].empty())
        {
            auto it=active[chain].lower_bound({p,0});
            if(it==active[chain].end())
                break;
            if((*it).first>last)
                break;
            int x=(*it).second;
            dfs2(x);
        }
        a=par[v[chain][last]];
    }
    while(b!=0&&niv[b]>niv[lca])
    {
        p=poz[b];
        chain=where[b];
        int last=v[chain].size();
        last--;
        if(where[b]==where[lca])
            last=poz[lca]-1;
        while(!active[chain].empty())
        {
            auto it=active[chain].lower_bound({p,0});
            if(it==active[chain].end())
                break;
            if((*it).first>last)
                break;
            int x=(*it).second;
            dfs2(x);
        }
        b=par[v[chain][last]];
    }
}
bool onchain(int x,int a,int b)
{
    return dist(a,x)+dist(x,b)==dist(a,b);
}
int curtest=0;
void solve()
{
    curtest++;
    cin>>n;
    timp=0;
    v.clear();
    suf.clear();
    active.clear();
    arb.clear();
    arb.shrink_to_fit();
    timp=0;
    for(int i=1;i<=n;i++)
    {
        muchii[i].clear();
        isheavy[i]=0;
    }
    for(int i=1;i<n;i++)
    {
        int a,b;
        cin>>a>>b;
        muchii[a].push_back(b);
        muchii[b].push_back(a);
    }
    niv[1]=1;
    par[1]=0;
    initdfs(1);
    cin>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>A[i]>>B[i];
        use[i]=0;
    }
    /*if(curtest!=18)
        return;
    if(onchain(A[1],A[2],B[2]))
        cout<<"Esti prost\n";*/
    buildhld();
    stiva.clear();
    for(int i=1;i<=m;i++)
    {
        addseg(A[i],B[i],i,+1);
        addnode(A[i],i,+1);
    }
    for(int i=1;i<=m;i++)
        if(!use[i])
            dfs1(i);
    reverse(stiva.begin(),stiva.end());
    for(int i=1;i<=m;i++)
    {
        use[i]=0;
        addseg(A[i],B[i],i,+1);
        addnode(B[i],i,+1);
    }
    int nrcomp=0;
    for(int i:stiva)
        if(!use[i])
        {
            nrcomp++;
            dfs2(i);
        }
    if(nrcomp==m)
        cout<<"Yes\n";
    else
        cout<<"No\n";
    /*for(int i=1;i<=m;i++)
        for(int j=1;j<=m;j++)
            if(i!=j)
            {
                if(onchain(A[j],A[i],B[i]))
                {
                    edges[j].push_back(i);
                    grad[i]++;
                }
                if(onchain(B[j],A[i],B[i]))
                {
                    edges[i].push_back(j);
                    grad[j]++;
                }
            }*/

}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>t;
    while(t--)
        solve();
    return 0;
}

Compilation message

jail.cpp: In function 'void buildhld()':
jail.cpp:85:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |             for(int i=0;i<nodes.size();i++)
      |                         ~^~~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from jail.cpp:1:
jail.cpp: In function 'void update(int, int, int, int, int, int, int, int)':
jail.cpp:113:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::set<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |     assert(nod<arb[chain].size());
      |            ~~~^~~~~~~~~~~~~~~~~~
jail.cpp: In function 'void query(int, int, int, int, int)':
jail.cpp:132:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::set<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |     assert(nod<arb[chain].size());
      |            ~~~^~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16732 KB Output is correct
2 Correct 2 ms 16732 KB Output is correct
3 Correct 3 ms 16732 KB Output is correct
4 Correct 12 ms 16732 KB Output is correct
5 Correct 25 ms 16912 KB Output is correct
6 Correct 3 ms 16728 KB Output is correct
7 Correct 3 ms 16732 KB Output is correct
8 Correct 7 ms 16988 KB Output is correct
9 Correct 52 ms 19468 KB Output is correct
10 Correct 56 ms 61172 KB Output is correct
11 Correct 14 ms 16728 KB Output is correct
12 Correct 88 ms 16732 KB Output is correct
13 Correct 209 ms 80652 KB Output is correct
14 Correct 208 ms 79508 KB Output is correct
15 Correct 1148 ms 99720 KB Output is correct
16 Correct 3423 ms 154328 KB Output is correct
17 Correct 458 ms 111600 KB Output is correct
18 Correct 283 ms 78836 KB Output is correct
19 Correct 464 ms 106788 KB Output is correct
20 Correct 423 ms 106920 KB Output is correct
21 Correct 519 ms 110224 KB Output is correct
22 Correct 183 ms 69872 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16728 KB Output is correct
2 Correct 2 ms 16728 KB Output is correct
3 Correct 3 ms 16732 KB Output is correct
4 Correct 4 ms 16988 KB Output is correct
5 Correct 4 ms 16988 KB Output is correct
6 Correct 4 ms 16988 KB Output is correct
7 Correct 4 ms 16988 KB Output is correct
8 Correct 3 ms 16988 KB Output is correct
9 Correct 4 ms 16988 KB Output is correct
10 Correct 4 ms 16988 KB Output is correct
11 Correct 4 ms 16988 KB Output is correct
12 Correct 3 ms 16988 KB Output is correct
13 Correct 3 ms 16984 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16728 KB Output is correct
2 Correct 2 ms 16728 KB Output is correct
3 Correct 3 ms 16732 KB Output is correct
4 Correct 4 ms 16988 KB Output is correct
5 Correct 4 ms 16988 KB Output is correct
6 Correct 4 ms 16988 KB Output is correct
7 Correct 4 ms 16988 KB Output is correct
8 Correct 3 ms 16988 KB Output is correct
9 Correct 4 ms 16988 KB Output is correct
10 Correct 4 ms 16988 KB Output is correct
11 Correct 4 ms 16988 KB Output is correct
12 Correct 3 ms 16988 KB Output is correct
13 Correct 3 ms 16984 KB Output is correct
14 Correct 2 ms 16728 KB Output is correct
15 Correct 2 ms 16732 KB Output is correct
16 Correct 3 ms 16732 KB Output is correct
17 Correct 4 ms 16988 KB Output is correct
18 Correct 4 ms 16988 KB Output is correct
19 Correct 4 ms 16732 KB Output is correct
20 Correct 4 ms 16988 KB Output is correct
21 Correct 4 ms 16988 KB Output is correct
22 Correct 4 ms 16988 KB Output is correct
23 Correct 3 ms 16732 KB Output is correct
24 Correct 2 ms 16732 KB Output is correct
25 Correct 4 ms 16984 KB Output is correct
26 Correct 3 ms 16732 KB Output is correct
27 Correct 4 ms 16988 KB Output is correct
28 Correct 3 ms 16732 KB Output is correct

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16728 KB Output is correct
2 Correct 2 ms 16728 KB Output is correct
3 Correct 3 ms 16732 KB Output is correct
4 Correct 4 ms 16988 KB Output is correct
5 Correct 4 ms 16988 KB Output is correct
6 Correct 4 ms 16988 KB Output is correct
7 Correct 4 ms 16988 KB Output is correct
8 Correct 3 ms 16988 KB Output is correct
9 Correct 4 ms 16988 KB Output is correct
10 Correct 4 ms 16988 KB Output is correct
11 Correct 4 ms 16988 KB Output is correct
12 Correct 3 ms 16988 KB Output is correct
13 Correct 3 ms 16984 KB Output is correct
14 Correct 2 ms 16728 KB Output is correct
15 Correct 2 ms 16732 KB Output is correct
16 Correct 3 ms 16732 KB Output is correct
17 Correct 4 ms 16988 KB Output is correct
18 Correct 4 ms 16988 KB Output is correct
19 Correct 4 ms 16732 KB Output is correct
20 Correct 4 ms 16988 KB Output is correct
21 Correct 4 ms 16988 KB Output is correct
22 Correct 4 ms 16988 KB Output is correct
23 Correct 3 ms 16732 KB Output is correct
24 Correct 2 ms 16732 KB Output is correct
25 Correct 4 ms 16984 KB Output is correct
26 Correct 3 ms 16732 KB Output is correct
27 Correct 4 ms 16988 KB Output is correct
28 Correct 3 ms 16732 KB Output is correct
29 Correct 7 ms 16988 KB Output is correct
30 Correct 8 ms 17096 KB Output is correct
31 Runtime error 15 ms 34196 KB Execution killed with signal 11
32 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16728 KB Output is correct
2 Correct 2 ms 16728 KB Output is correct
3 Correct 3 ms 16732 KB Output is correct
4 Correct 4 ms 16988 KB Output is correct
5 Correct 4 ms 16988 KB Output is correct
6 Correct 4 ms 16988 KB Output is correct
7 Correct 4 ms 16988 KB Output is correct
8 Correct 3 ms 16988 KB Output is correct
9 Correct 4 ms 16988 KB Output is correct
10 Correct 4 ms 16988 KB Output is correct
11 Correct 4 ms 16988 KB Output is correct
12 Correct 3 ms 16988 KB Output is correct
13 Correct 3 ms 16984 KB Output is correct
14 Correct 2 ms 16728 KB Output is correct
15 Correct 2 ms 16732 KB Output is correct
16 Correct 3 ms 16732 KB Output is correct
17 Correct 4 ms 16988 KB Output is correct
18 Correct 4 ms 16988 KB Output is correct
19 Correct 4 ms 16732 KB Output is correct
20 Correct 4 ms 16988 KB Output is correct
21 Correct 4 ms 16988 KB Output is correct
22 Correct 4 ms 16988 KB Output is correct
23 Correct 3 ms 16732 KB Output is correct
24 Correct 2 ms 16732 KB Output is correct
25 Correct 4 ms 16984 KB Output is correct
26 Correct 3 ms 16732 KB Output is correct
27 Correct 4 ms 16988 KB Output is correct
28 Correct 3 ms 16732 KB Output is correct
29 Correct 7 ms 16988 KB Output is correct
30 Correct 8 ms 17096 KB Output is correct
31 Runtime error 15 ms 34196 KB Execution killed with signal 11
32 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16732 KB Output is correct
2 Correct 2 ms 16732 KB Output is correct
3 Correct 3 ms 16732 KB Output is correct
4 Correct 2 ms 16732 KB Output is correct
5 Correct 14 ms 16904 KB Output is correct
6 Correct 4 ms 16988 KB Output is correct
7 Correct 3 ms 16988 KB Output is correct
8 Correct 2 ms 16900 KB Output is correct
9 Correct 3 ms 16732 KB Output is correct
10 Correct 2 ms 16732 KB Output is correct
11 Correct 2 ms 16732 KB Output is correct
12 Incorrect 7 ms 16984 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16732 KB Output is correct
2 Correct 2 ms 16732 KB Output is correct
3 Correct 3 ms 16732 KB Output is correct
4 Correct 12 ms 16732 KB Output is correct
5 Correct 25 ms 16912 KB Output is correct
6 Correct 3 ms 16728 KB Output is correct
7 Correct 3 ms 16732 KB Output is correct
8 Correct 7 ms 16988 KB Output is correct
9 Correct 52 ms 19468 KB Output is correct
10 Correct 56 ms 61172 KB Output is correct
11 Correct 14 ms 16728 KB Output is correct
12 Correct 88 ms 16732 KB Output is correct
13 Correct 209 ms 80652 KB Output is correct
14 Correct 208 ms 79508 KB Output is correct
15 Correct 1148 ms 99720 KB Output is correct
16 Correct 3423 ms 154328 KB Output is correct
17 Correct 458 ms 111600 KB Output is correct
18 Correct 283 ms 78836 KB Output is correct
19 Correct 464 ms 106788 KB Output is correct
20 Correct 423 ms 106920 KB Output is correct
21 Correct 519 ms 110224 KB Output is correct
22 Correct 183 ms 69872 KB Output is correct
23 Correct 2 ms 16728 KB Output is correct
24 Correct 2 ms 16728 KB Output is correct
25 Correct 3 ms 16732 KB Output is correct
26 Correct 4 ms 16988 KB Output is correct
27 Correct 4 ms 16988 KB Output is correct
28 Correct 4 ms 16988 KB Output is correct
29 Correct 4 ms 16988 KB Output is correct
30 Correct 3 ms 16988 KB Output is correct
31 Correct 4 ms 16988 KB Output is correct
32 Correct 4 ms 16988 KB Output is correct
33 Correct 4 ms 16988 KB Output is correct
34 Correct 3 ms 16988 KB Output is correct
35 Correct 3 ms 16984 KB Output is correct
36 Correct 2 ms 16728 KB Output is correct
37 Correct 2 ms 16732 KB Output is correct
38 Correct 3 ms 16732 KB Output is correct
39 Correct 4 ms 16988 KB Output is correct
40 Correct 4 ms 16988 KB Output is correct
41 Correct 4 ms 16732 KB Output is correct
42 Correct 4 ms 16988 KB Output is correct
43 Correct 4 ms 16988 KB Output is correct
44 Correct 4 ms 16988 KB Output is correct
45 Correct 3 ms 16732 KB Output is correct
46 Correct 2 ms 16732 KB Output is correct
47 Correct 4 ms 16984 KB Output is correct
48 Correct 3 ms 16732 KB Output is correct
49 Correct 4 ms 16988 KB Output is correct
50 Correct 3 ms 16732 KB Output is correct
51 Correct 7 ms 16988 KB Output is correct
52 Correct 8 ms 17096 KB Output is correct
53 Runtime error 15 ms 34196 KB Execution killed with signal 11
54 Halted 0 ms 0 KB -