oj.uz

답안 #927367

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
927367 2024-02-14T19:09:01 Z andrei_boaca Jail (JOI22_jail) C++17
5 / 100
 3595 ms 156512 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[1200005],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});
}
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);
        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);
            }
        }
        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);
            }
        }
        b=par[v[chain][last]];
    }
}
void dfs1(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;
        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[a]==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(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;
        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[a]==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]];
    }
}
void solve()
{
    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;
    initdfs(1);
    cin>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>A[i]>>B[i];
        use[i]=0;
    }
    buildhld();
    stiva.clear();
    for(int i=1;i<=m;i++)
    {
        addseg(A[i],B[i],i,+1);
        addnode(B[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(A[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:111:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::set<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |     assert(nod<arb[chain].size());
      |            ~~~^~~~~~~~~~~~~~~~~~
jail.cpp: In function 'void query(int, int, int, int, int)':
jail.cpp:128:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::set<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |     assert(nod<arb[chain].size());
      |            ~~~^~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 16728 KB Output is correct
2 Correct 2 ms 16732 KB Output is correct
3 Correct 2 ms 16732 KB Output is correct
4 Correct 14 ms 16936 KB Output is correct
5 Correct 24 ms 16732 KB Output is correct
6 Correct 3 ms 16732 KB Output is correct
7 Correct 3 ms 16728 KB Output is correct
8 Correct 7 ms 16988 KB Output is correct
9 Correct 53 ms 19468 KB Output is correct
10 Correct 52 ms 63248 KB Output is correct
11 Correct 14 ms 16732 KB Output is correct
12 Correct 96 ms 16944 KB Output is correct
13 Correct 207 ms 82836 KB Output is correct
14 Correct 196 ms 81644 KB Output is correct
15 Correct 1101 ms 101672 KB Output is correct
16 Correct 3595 ms 156512 KB Output is correct
17 Correct 475 ms 113904 KB Output is correct
18 Correct 284 ms 80676 KB Output is correct
19 Correct 427 ms 109264 KB Output is correct
20 Correct 418 ms 108780 KB Output is correct
21 Correct 526 ms 112464 KB Output is correct
22 Correct 163 ms 71532 KB Output is correct

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 16728 KB Output is correct
2 Correct 2 ms 16728 KB Output is correct
3 Correct 3 ms 16744 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 3 ms 17032 KB Output is correct
8 Correct 4 ms 16988 KB Output is correct
9 Correct 3 ms 16988 KB Output is correct
10 Runtime error 15 ms 34032 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 16728 KB Output is correct
2 Correct 2 ms 16728 KB Output is correct
3 Correct 3 ms 16744 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 3 ms 17032 KB Output is correct
8 Correct 4 ms 16988 KB Output is correct
9 Correct 3 ms 16988 KB Output is correct
10 Runtime error 15 ms 34032 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 16728 KB Output is correct
2 Correct 2 ms 16728 KB Output is correct
3 Correct 3 ms 16744 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 3 ms 17032 KB Output is correct
8 Correct 4 ms 16988 KB Output is correct
9 Correct 3 ms 16988 KB Output is correct
10 Runtime error 15 ms 34032 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 16728 KB Output is correct
2 Correct 2 ms 16728 KB Output is correct
3 Correct 3 ms 16744 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 3 ms 17032 KB Output is correct
8 Correct 4 ms 16988 KB Output is correct
9 Correct 3 ms 16988 KB Output is correct
10 Runtime error 15 ms 34032 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 16732 KB Output is correct
2 Correct 2 ms 16732 KB Output is correct
3 Correct 2 ms 16732 KB Output is correct
4 Correct 2 ms 16732 KB Output is correct
5 Correct 14 ms 16912 KB Output is correct
6 Correct 4 ms 16988 KB Output is correct
7 Correct 3 ms 16988 KB Output is correct
8 Runtime error 19 ms 33936 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 16728 KB Output is correct
2 Correct 2 ms 16732 KB Output is correct
3 Correct 2 ms 16732 KB Output is correct
4 Correct 14 ms 16936 KB Output is correct
5 Correct 24 ms 16732 KB Output is correct
6 Correct 3 ms 16732 KB Output is correct
7 Correct 3 ms 16728 KB Output is correct
8 Correct 7 ms 16988 KB Output is correct
9 Correct 53 ms 19468 KB Output is correct
10 Correct 52 ms 63248 KB Output is correct
11 Correct 14 ms 16732 KB Output is correct
12 Correct 96 ms 16944 KB Output is correct
13 Correct 207 ms 82836 KB Output is correct
14 Correct 196 ms 81644 KB Output is correct
15 Correct 1101 ms 101672 KB Output is correct
16 Correct 3595 ms 156512 KB Output is correct
17 Correct 475 ms 113904 KB Output is correct
18 Correct 284 ms 80676 KB Output is correct
19 Correct 427 ms 109264 KB Output is correct
20 Correct 418 ms 108780 KB Output is correct
21 Correct 526 ms 112464 KB Output is correct
22 Correct 163 ms 71532 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 16744 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 3 ms 17032 KB Output is correct
30 Correct 4 ms 16988 KB Output is correct
31 Correct 3 ms 16988 KB Output is correct
32 Runtime error 15 ms 34032 KB Execution killed with signal 11
33 Halted 0 ms 0 KB -