oj.uz

Submission #929669

# Submission time Handle Problem Language Result Execution time Memory
929669 2024-02-18T07:20:03 Z ttamx Usmjeri (COCI17_usmjeri) C++14
126 / 140
 1749 ms 71616 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){
        auto [ai,ui,vi]=i;
        auto [aj,uj,vj]=j;
        if(lv[ai]!=lv[aj])return lv[ai]<lv[aj];
        if(disc[ui]!=disc[uj])return disc[ui]>disc[uj];
        return disc[vi]>disc[vj];
    });
    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:126:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  126 |         auto [ai,ui,vi]=i;
      |              ^
usmjeri.cpp:127:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  127 |         auto [aj,uj,vj]=j;
      |              ^
usmjeri.cpp: In function 'int main()':
usmjeri.cpp:132:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  132 |     for(auto [a,u,v]:qr){
      |              ^

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 487 ms 42444 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 757 ms 71616 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 26712 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 8 ms 26716 KB Output is correct
2 Correct 9 ms 26972 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 27224 KB Output is correct
2 Correct 8 ms 26972 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 27228 KB Output is correct
2 Correct 8 ms 26972 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1405 ms 49088 KB Output is correct
2 Correct 1313 ms 48896 KB Output is correct
3 Correct 462 ms 37580 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1224 ms 48068 KB Output is correct
2 Correct 1233 ms 47276 KB Output is correct
3 Correct 979 ms 39112 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1267 ms 49064 KB Output is correct
2 Correct 1527 ms 49264 KB Output is correct
3 Correct 876 ms 39708 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1678 ms 48300 KB Output is correct
2 Correct 1749 ms 49488 KB Output is correct
3 Correct 189 ms 37516 KB Output is correct