Submission #1279687

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279687		davele	LOSTIKS (INOI20_lostiks)	C++20	100 / 100	1376 ms	608176 KiB

Main

// nhan xet quan trong cho bai nay:
//co the thay m =20 da goi y bai nay la dp bitmask, van de o day la co toi n dinh can luu trang thai
//mot cach giam so luong trang thai hieu qua do la loai bo cac trang thai khong quan trong
//noi cach khac, voi moi canh bi cam ta chi can quan tam va danh dau cac dinh dau mut cua canh nay
//
//No la ki thuat khong cu, co dieu da bi lang quen
//
//Ngoai ra ta co 1 chung minh bo tro nhu sau
//vi no la cay, nen chi ton tai duy nhat 1 duong di tu u den v -> cac duong di kieu gi thi kieu cung di qua dong nay
//
//suy ra voi cac bai mo khoa -> phai lay chia truoc roi tu chia di den o khoa
//ngoai ra nho no la cay ta cung co the de dang kiem tra xem doan duong bat buoc phai qua nhung loai khoa nao
//Het roi!
//
//A mot nhan xet lam giam so chieu
//tu s ta chi di den dinh gan hon (no khong dung voi moi trang thai dp nhung se dung voi ket qua toi uu)

#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define fi first
#define se second
#define vi vector <int>
#define pq priority_queue
#define MASK(i) (1ll<<(i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define x0 ___x0
#define y0 ___y0
#define div   ___div
#define next   ___next
#define prev   ___prev
#define left   ___left
#define right   ___right
#define pos pisosi
#define pb push_back
#define pf push_front
using namespace std;

//const int mod = ;
//void add (int &a, const int&b){
//    a+=b;
//    if (a>=mod) a-=mod;
//}
//
//void sub (int&a, const int&b){
//    a-=b;
//    if (a<0) a+=mod;
//}
//
//void mul (int&a, const int&b){
//    a*=b;
//    a%=mod;
//}

template<class X, class Y>
    bool minimize(X &x, const Y&y){
        if (x<=y) return false;
        else{
            x = y;
            return true;
        }
    }
template<class X, class Y>
    bool maximize (X &x, const Y&y){
        if (x>=y) return false;
        else{
            x = y;
            return true;
        }
    }

/////////////////////////////////////////////////////////////////////////////////

//// dang nhap ham
//#ifndef davele
//
//#endif // davele
//
//// chay thu ham main:
//
//#ifdef davele
//
//#endif // davele

////////////////////////////////////////////////////////////////////////////
//const int lim = , limit = , inf = ;
const string name = "treemaze";
const int lim = 1100000, limit = lim+5, inf = 1e18;

int n, m, s, t;
int key[limit];
pii edge[limit];
int maskval[limit];
vector <pii> adj[limit];
int pos[limit], numlca, dslca[2*limit];
int rmq[2*limit][21];
int dp[limit][21];
int st[limit], en[limit], cntdfs;
int opt[limit];

int h[limit], summask[limit];

void dfs (int u, int pre){
    st[u]=++cntdfs;
    pos[u] = ++numlca;
    dslca[numlca] = u;
    for (pii x:adj[u]){
        int v = x.fi, id = x.se;
        if (v==pre) continue;
        h[v] = h[u]+1;
        summask[v] = summask[u] + maskval[id];
        dfs(v, u);
        dslca[++numlca] = u;
    }
    en[u] = cntdfs;
}

int getmin (int u, int v){
    if (h[u]<h[v]) return u;
    return v;
}

int lca (int u, int v){
    int l = pos[u], r = pos[v];
    if (l>r) swap(l, r);
    int tm = 31-__builtin_clz(r-l+1);
    return getmin (rmq[l][tm], rmq[r-MASK(tm)+1][tm]);
}

int getbit (int u, int v){
    return summask[u]^summask[v];
}

int dist (int u, int v){
    int LCA = lca(u, v);
    return h[u]+h[v]-2*h[LCA];
}

bool parchild (int pare, int chil){
    return (pare&chil)==chil;
}

void process(){
    dfs (1, 1);
    for (int i=1; i<=numlca; i++) rmq[i][0] = dslca[i];
    for (int i=1; i<=20; i++){
        for (int j=1; j+MASK(i)-1<=numlca; j++){
            rmq[j][i] = getmin (rmq[j][i-1], rmq[j+MASK(i-1)][i-1]);
        }
    }
    for (int i=0; i<m; i++){
        int u = edge[i].fi, v = edge[i].se;
        if (h[u]<h[v]) swap(u, v);
        if (st[s]>=st[u] && st[s]<=en[u]) opt[i] = u;
        else opt[i] = v;
    }
    // xu ly truong hop di mot mach tu s den t
    if (getbit(s,t)==0){
        cout<<dist(s, t);
        return;
    }
    //
    int ALLMASK = MASK(m)-1;
    for (int i=1; i<=ALLMASK; i++) for (int j=0; j<m; j++)
        dp[i][j] = inf;
    // xu ly truong hop 1 bit
    for (int i=0; i<m; i++){
        int tmp = key[i];
        //
        if (getbit(s, tmp)==0 && getbit(tmp, opt[i])==0){
            minimize (dp[MASK(i)][i], dist(s,tmp)+dist(tmp, opt[i]));
        }
//        cerr<<getbit(s, tmp)<<"\n";
//        cerr<<i<<" "<<tmp<<" "<<fiu<<" "<<seu<<" "<<dp[MASK(i)][i][0]<<" "<<dp[MASK(i)][i][1]<<"\n";
    }
    int ret = inf;
    //
    for (int mask=1; mask<=ALLMASK; mask++){
        for (int i=0; i<m; i++) if (MASK(i)&mask){
                if (dp[mask][i]==inf) continue;
                int u = opt[i];
//                cerr<<mask<<" "<<i<<" "<<j<<" "<<u<<" "<<dp[mask][i][j]<<"\n";
                if (parchild(mask, getbit(u, t))){
//                    cerr<<u<<" "<<mask<<" "<<dp[mask][i][j]<<" "<<dist(u, t)<<"\n";
                    minimize (ret, dp[mask][i]+dist(u, t));
                }
                //
                for (int z=0; z<m; z++) if (BIT(mask, z)==0){
                    int khoa = key[z];
                    int tmp = getbit(u, khoa);
                    if (!parchild(mask, tmp)) continue;
                    int newmask = mask^MASK(z);
                    if (parchild(mask, getbit(khoa, opt[z]))){
                        minimize (dp[newmask][z], dp[mask][i]+dist(u, khoa)+dist(khoa, opt[z]));
                    }
            }
        }
    }
    if (ret==inf) cout<<"-1";
    else cout<<ret;
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //
//    if (fopen((name+".inp").c_str(), "r")){
//        freopen ((name+".inp").c_str(), "r", stdin);
//        freopen ((name+".out").c_str(), "w", stdout);
//    }
    //
    cin>>n>>s>>t;
    m = 0;
    for (int i=1; i<n; i++){
        int u, v, H;
        cin>>u>>v>>H;
        if (H>0){
            key[m] = H;
            edge[m] = {u, v};
            maskval[i] = MASK(m);
            m++;
        }
        else{
            maskval[i] = 0;
        }
        adj[u].pb({v, i});
        adj[v].pb({u, i});
    }
    process();
}

• Subtask 1: 23 / 23
• Subtask 2: 36 / 36
• Subtask 3: 41 / 41