oj.uz

Submission #1095666

# Submission time Handle Problem Language Result Execution time Memory
1095666 2024-10-02T21:51:01 Z tfgs Usmjeri (COCI17_usmjeri) C++17
28 / 140
 399 ms 157772 KB 
#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#endif

#define f first
#define s second
template<class T> using V = vector<T>; 
using vi = V<int>;
using vb = V<bool>;
using vs = V<string>;

#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x) 
#define len(x) (int)((x).size())
#define rsz resize
#define ins insert
#define ft front()
#define bk back()
#define pb push_back
#define lb lower_bound
#define ub upper_bound
template<class T> int lwb(V<T>& a, const T& b) { return lb(all(a),b)-begin(a); }
template<class T> int upb(V<T>& a, const T& b) { return ub(all(a),b)-begin(a); }
template<class T> bool ckmin(T& a, const T& b) { return a > b ? a=b, true : false; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a=b, true : false; }
#define pct __builtin_popcount
#define ctz __builtin_ctz
#define clz __builtin_clz
constexpr int p2(int x) { return (int)1 << x; }
constexpr int bits(int x) { return x == 0 ? 0 : 31-clz(x); } // floor(log2(x)) 

using i64 = long long;
template<class T>
constexpr T power(T a, i64 b) {
    T res {1};
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
}
constexpr i64 mul(i64 a, i64 b, i64 p) {
    i64 res = a * b - i64(1.L * a * b / p) * p;
    res %= p;
    if (res < 0) {
        res += p;
    }
    return res;
}

template<i64 P>
struct MInt {
    i64 x;
    constexpr MInt() : x {0} {}
    constexpr MInt(i64 x) : x {norm(x % getMod())} {}
    
    static inline i64 Mod;
    constexpr static i64 getMod() {
        if (P > 0) {
            return P;
        } else {
            return Mod;
        }
    }
    constexpr static void setMod(i64 Mod_) {
        Mod = Mod_;
    }
    constexpr i64 norm(i64 x) const {
        if (x < 0) {
            x += getMod();
        }
        if (x >= getMod()) {
            x -= getMod();
        }
        return x;
    }
    constexpr i64 val() const {
        return x;
    }
    constexpr MInt operator-() const {
        MInt res;
        res.x = norm(getMod() - x);
        return res;
    }
    constexpr MInt inv() const {
        return power(*this, getMod() - 2);
    }
    constexpr MInt &operator*=(MInt rhs) & {
        if (getMod() < (1ULL << 31)) {
            x = x * rhs.x % int(getMod());
        } else {
            x = mul(x, rhs.x, getMod());
        }
        return *this;
    }
    constexpr MInt &operator+=(MInt rhs) & {
        x = norm(x + rhs.x);
        return *this;
    }
    constexpr MInt &operator-=(MInt rhs) & {
        x = norm(x - rhs.x);
        return *this;
    }
    constexpr MInt &operator/=(MInt rhs) & {
        return *this *= rhs.inv();
    }
    friend constexpr MInt operator*(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res *= rhs;
        return res;
    }
    friend constexpr MInt operator+(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res += rhs;
        return res;
    }
    friend constexpr MInt operator-(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res -= rhs;
        return res;
    }
    friend constexpr MInt operator/(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res /= rhs;
        return res;
    }
    friend constexpr std::istream &operator>>(std::istream &is, MInt &a) {
        i64 v = 69;
        is >> v;
        a = MInt(v);
        return is;
    }
    friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) {
        return os << a.val();
    }
    friend constexpr bool operator==(MInt lhs, MInt rhs) {
        return lhs.val() == rhs.val();
    }
    friend constexpr bool operator!=(MInt lhs, MInt rhs) {
        return lhs.val() != rhs.val();
    }
    friend constexpr bool operator<(MInt lhs, MInt rhs) {
        return lhs.val() < rhs.val();
    }
};
 
template<>
i64 MInt<0>::Mod = 998244353;
 
constexpr int P = 1000000007;
using Z = MInt<P>;

Z ans=1;

const int LOG=19;
V<vi>up,g;
V<V<array<int,2>>>queries;
vi mentions,dep,pseudo_map;
void init_lca(int u,int p){
    for(int v:g[u])if(v!=p){
        up[v][0]=u;
        for(int i=1;i<LOG;i++){
            up[v][i]=up[up[v][i-1]][i-1];
        }
        dep[v]=dep[u]+1;
        init_lca(v,u);
    }
}
int jump(int u,int x){
    for(int i=LOG-1;i>=0;i--)if(x&p2(i)){
        u=up[u][i];
    }
    return u;
}
int get_lca(int u,int v){
    if(dep[u]<dep[v])swap(u,v);
    u=jump(u,dep[u]-dep[v]);
    if(u==v)return u;
    for(int i=LOG-1;i>=0;i--)if(up[u][i]!=up[v][i]){
        u=up[u][i];
        v=up[v][i];
    }
    return up[u][0];
}
int rec(int u,int p){
    int ind=0;
    vi unres;
    for(int v:g[u])if(v!=p){
        unres.pb(rec(v,u));
        pseudo_map[v]=ind++;
    }
    unres.pb(mentions[u]);
    pseudo_map[u]=ind;
    V<vi>h(ind);
    vi col(ind,-1);
    for(auto[x,y]:queries[u]){
        x=pseudo_map[x];
        y=pseudo_map[y];
        unres[x]--;
        unres[y]--;
    }
    for(auto[x,y]:queries[u]){
        if(x==u||y==u)continue;
        x=pseudo_map[x];
        y=pseudo_map[y];
        h[x].pb(y);
        h[y].pb(x);
    }
    int up_col=-1;
    auto label_bip=[&](auto&&self,int u,int cur_col)->void{
        col[u]=cur_col;
        if(unres[u]){
            if(up_col==-1)up_col=cur_col;
            if(up_col!=cur_col){
                ans=0;
            }
        }
        for(int v:h[u]){
            if(col[v]==-1)self(self,v,1^cur_col);
            else if(col[v]==cur_col)ans=0;
        }
    };
    for(int u=0;u<ind;u++)if(col[u]==-1){
        label_bip(label_bip,u,0);
        if(up_col==-1)ans*=2;
    }
    int ret=0;
    for(int i=0;i<=ind;i++)ret+=unres[i];
    return ret;
}
void solve() {
    int n,q;cin>>n>>q;
    g.resize(n);
    dep.rsz(n);
    mentions.rsz(n);
    up.rsz(n,vi(LOG));
    queries.rsz(n);
    pseudo_map.rsz(n);
    for(int i=0;i<n-1;i++){
        int u,v;cin>>u>>v;u--;v--;
        g[u].pb(v);g[v].pb(u);
    }
    init_lca(0,-1);
    while(q--){
        int u,v;cin>>u>>v;u--;v--;
        int lca=get_lca(u,v);
        mentions[u]++;mentions[v]++;
        if(lca==u){
            queries[lca].pb({u,jump(v,dep[v]-dep[lca]-1)});
        }else if(lca==v){
            queries[lca].pb({jump(u,dep[u]-dep[lca]-1),v});
        }else{
            queries[lca].pb({jump(u,dep[u]-dep[lca]-1),jump(v,dep[v]-dep[lca]-1)});
        }
    }
    rec(0,-1);
    cout<<ans<<'\n';
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 55120 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 277 ms 157772 KB Output is correct

Subtask #3
0 / 14.0

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

Subtask #4
0 / 14.0

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

Subtask #5
0 / 14.0

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

Subtask #6
0 / 14.0

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

Subtask #7
0 / 14.0

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

Subtask #8
0 / 14.0

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

Subtask #9
0 / 14.0

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

Subtask #10
0 / 14.0

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