oj.uz

Submission #929660

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

using namespace std;

using t3 = tuple<int,int,int>;

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

int n,m;
vector<int> adj[N];
int pa[N],lv[N],sz[N],hv[N],hd[N],disc[N];
int timer;
vector<t3> qr;
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){
    sz[u]=1;
    for(auto v:adj[u])if(v!=pa[u]){
        pa[v]=u;
        lv[v]=lv[u]+1;
        dfs(v);
        sz[u]+=sz[v];
        if(sz[v]>sz[hv[u]])hv[u]=v;
    }
}

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

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]];
    }
    return lv[u]<lv[v]?u:v;
}

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]];
    }
    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]];
    }
    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=0;i<m;i++){
        int u,v;
        cin >> u >> v;
        qr.emplace_back(lca(u,v),u,v);
    }
    sort(qr.begin(),qr.end(),[&](t3 i,t3 j){
        int u=get<0>(i),v=get<0>(j);
        return lv[u]<lv[v]||(lv[u]==lv[u]&&disc[u]<disc[v]);
    });
    for(auto [a,u,v]:qr){
        Node pu=query(u,a);
        Node pv=query(v,a);
        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,a,1);
            update(v,a,-1);
        }else{
            if(!mn){
                ans*=2;
                if(ans>=MOD)ans-=MOD;
            }
            update(u,a,-1);
            update(v,a,1);
        }
    }
    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;
}

Compilation message

usmjeri.cpp: In lambda function:
usmjeri.cpp:127:35: warning: self-comparison always evaluates to true [-Wtautological-compare]
  127 |         return lv[u]<lv[v]||(lv[u]==lv[u]&&disc[u]<disc[v]);
      |                              ~~~~~^~~~~~~
usmjeri.cpp: In function 'int main()':
usmjeri.cpp:129:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  129 |     for(auto [a,u,v]:qr){
      |              ^

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 464 ms 42284 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 780 ms 71792 KB Output is correct

Subtask #3
0 / 14.0

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

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 38 ms 54100 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 29 ms 54868 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 30 ms 54860 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1370 ms 49052 KB Output is correct
2 Execution timed out 2062 ms 48756 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1124 ms 47452 KB Output is correct
2 Correct 1350 ms 47964 KB Output is correct
3 Correct 1025 ms 39876 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1181 ms 47492 KB Output is correct
2 Correct 1787 ms 48020 KB Output is correct
3 Correct 850 ms 40488 KB Output is correct

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1535 ms 48048 KB Output is correct
2 Correct 1668 ms 47676 KB Output is correct
3 Runtime error 138 ms 75012 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -