oj.uz

Submission #929615

# Submission time Handle Problem Language Result Execution time Memory
929615 2024-02-18T06:56:38 Z ttamx Usmjeri (COCI17_usmjeri) C++14
98 / 140
 1537 ms 78360 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){
        return disc[get<0>(i)]<disc[get<0>(j)];
    });
    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==1&&mn==-1)cout << 0,exit(0);
        if(mx==1){
            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){
            ans*=2;
            if(ans>=MOD)ans-=MOD;
        }
    }
    cout << ans;
}

Compilation message

usmjeri.cpp: In function 'int main()':
usmjeri.cpp:128:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  128 |     for(auto [a,u,v]:qr){
      |              ^

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 468 ms 46284 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 798 ms 78360 KB Output is correct

Subtask #3
0 / 14.0

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

Subtask #4
0 / 14.0

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

Subtask #5
14.0 / 14.0

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

Subtask #6
0 / 14.0

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

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1302 ms 55184 KB Output is correct
2 Correct 1266 ms 55196 KB Output is correct
3 Correct 449 ms 41092 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1277 ms 56660 KB Output is correct
2 Correct 1203 ms 56912 KB Output is correct
3 Correct 1063 ms 43528 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1178 ms 56400 KB Output is correct
2 Correct 1453 ms 55716 KB Output is correct
3 Correct 873 ms 44356 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1505 ms 56908 KB Output is correct
2 Correct 1537 ms 55096 KB Output is correct
3 Correct 130 ms 41164 KB Output is correct