oj.uz

Submission #1095615

# Submission time Handle Problem Language Result Execution time Memory
1095615 2024-10-02T17:25:58 Z tfgs Usmjeri (COCI17_usmjeri) C++17
0 / 140
 207 ms 168784 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)) 

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){
    up[u][0]=p;
    for(int v:g[u])if(v!=p){
        dep[v]=dep[u]+1;
        init_lca(v,u);
    }
    for(int i=1;i<LOG;i++){
        up[u][i]=up[u][i-1]==-1?-1:up[up[u][i-1]][i-1];
    }
}
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)u=jump(u,1);
    return u;
}
int ans=1;
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
0 / 14.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 14.0

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

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 860 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 3 ms 2652 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 3 ms 2804 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

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

Subtask #8
0 / 14.0

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

Subtask #9
0 / 14.0

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

Subtask #10
0 / 14.0

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