oj.uz

Submission #929744

# Submission time Handle Problem Language Result Execution time Memory
929744 2024-02-18T07:48:56 Z ttamx Usmjeri (COCI17_usmjeri) C++14
70 / 140
 2000 ms 109696 KB 
#include<bits/stdc++.h>

using namespace std;

const int N=3e5+5;
const int K=1<<20;
const int LG=19;
const int MOD=1e9+7;

int n,m;
vector<int> adj[N],adj2[N];
int pa[N][LG],lv[N],sz[N],hv[N],hd[N],disc[N];
bool vis[N],vis2[N];
int qu[N],qv[N],a[N],qqu[N],qqv[N];
int timer;
vector<int> qr[N];
int ans=1;

struct Node{
    int mn,mx;
    Node():mn(0),mx(0){}
    Node(int x):mn(x),mx(x){}
    Node(int _mn,int _mx):mn(_mn),mx(_mx){}
    friend Node operator+(const Node &lhs,const Node &rhs){
        return Node(min(lhs.mn,rhs.mn),max(lhs.mx,rhs.mx));
    }
    Node &operator+=(const Node &rhs){
        return *this=*this+rhs;
    }
};

struct Segtree{
    Node t[K],lz[K];
    void push(int l,int r,int i){
        t[i]+=lz[i];
        if(l<r){
            lz[i*2]+=lz[i];
            lz[i*2+1]+=lz[i];
        }
        lz[i]=Node();
    }
    void update(int l,int r,int i,int x,int y,int v){
        push(l,r,i);
        if(y<l||r<x)return;
        if(x<=l&&r<=y)return lz[i]=Node(v),push(l,r,i);
        int m=(l+r)/2;
        update(l,m,i*2,x,y,v);
        update(m+1,r,i*2+1,x,y,v);
        t[i]=t[i*2]+t[i*2+1];
    }
    void update(int x,int y,int v){
        update(1,n,1,x,y,v);
    }
    Node query(int l,int r,int i,int x,int y){
        push(l,r,i);
        if(y<l||r<x)return Node();
        if(x<=l&&r<=y)return t[i];
        int m=(l+r)/2;
        return query(l,m,i*2,x,y)+query(m+1,r,i*2+1,x,y);
    }
    Node query(int x,int y){
        return query(1,n,1,x,y);
    }
}s;

void dfs(int u,int p=0){
    sz[u]=1;
    for(auto v:adj[u])if(v!=p){
        pa[v][0]=u;
        for(int i=1;i<LG;i++)pa[v][i]=pa[pa[v][i-1]][i-1];
        lv[v]=lv[u]+1;
        dfs(v,u);
        sz[u]+=sz[v];
        if(sz[v]>sz[hv[u]])hv[u]=v;
    }
}

void hld(int u,int p=0){
    disc[u]=++timer;
    if(!hd[u])hd[u]=u;
    if(hv[u])hd[hv[u]]=hd[u],hld(hv[u],u);
    for(auto v:adj[u])if(v!=p&&v!=hv[u])hld(v,u);
}

int lca(int u,int v){
    while(hd[u]!=hd[v]){
        if(lv[hd[u]]<lv[hd[v]])swap(u,v);
        u=pa[hd[u]][0];
    }
    return lv[u]<lv[v]?u:v;
}

int jump(int u,int tar){
    for(int i=LG-1;i>=0;i--)if(lv[pa[u][i]]>=tar)u=pa[u][i];
    return u;
}

void update(int u,int a,int val){
    while(hd[u]!=hd[a]){
        s.update(disc[hd[u]],disc[u],val);
        u=pa[hd[u]][0];
    }
    s.update(disc[a]+1,disc[u],val);
}

Node query(int u,int a){
    Node res{};
    while(hd[u]!=hd[a]){
        res+=s.query(disc[hd[u]],disc[u]);
        u=pa[hd[u]][0];
    }
    res+=s.query(disc[a]+1,disc[u]);
    return res;
}

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> m;
    for(int i=1;i<n;i++){
        int u,v;
        cin >> u >> v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }
    dfs(1);
    hld(1);
    for(int i=1;i<=m;i++){
        cin >> qu[i] >> qv[i];
        a[i]=lca(qu[i],qv[i]);
        qr[a[i]].emplace_back(i);
        if(lv[qu[i]]>lv[a[i]])adj2[qqu[i]=jump(qu[i],lv[a[i]]+1)].emplace_back(i);
        if(lv[qv[i]]>lv[a[i]])adj2[qqv[i]=jump(qv[i],lv[a[i]]+1)].emplace_back(i);
    }
    queue<int> q;
    q.emplace(1);
    vis[1]=true;
    while(!q.empty()){
        int an=q.front();
        q.pop();
        for(auto v:adj[an])if(!vis[v]){
            vis[v]=true;
            q.emplace(v);
        }
        function<void(int)> solve=[&](int i){
            if(vis2[i])return;
            vis2[i]=true;
            int u=qu[i],v=qv[i];
            Node pu=query(u,an);
            Node pv=query(v,an);
            int mx=max(pu.mx,-pv.mn);
            int mn=min(pu.mn,-pv.mx);
            if(mx&&mn)cout << 0,exit(0);
            if(mx){
                update(u,an,1);
                update(v,an,-1);
            }else{
                if(!mn){
                    ans*=2;
                    if(ans>=MOD)ans-=MOD;
                }
                update(u,an,-1);
                update(v,an,1);
            }
            if(qqu[i])for(auto x:adj2[qqu[i]])solve(x);
            if(qqv[i])for(auto x:adj2[qqv[i]])solve(x);
        };
        for(auto i:qr[an])solve(i);
    }
    for(int i=2;i<=n;i++){
        Node tmp=s.query(i,i);
        if(tmp.mn&&tmp.mx)cout << 0,exit(0);
        if(!tmp.mn&&!tmp.mx){
            ans*=2;
            if(ans>=MOD)ans-=MOD;
        }
    }
    cout << ans;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 562 ms 70992 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 955 ms 109696 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 50012 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 50012 KB Output is correct
2 Correct 11 ms 50008 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 50268 KB Output is correct
2 Correct 13 ms 50312 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 50520 KB Output is correct
2 Correct 12 ms 50268 KB Output is correct

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2049 ms 86284 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2095 ms 87892 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2068 ms 87472 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2047 ms 87564 KB Time limit exceeded
2 Halted 0 ms 0 KB -