Submission #805785

# Submission time Handle Problem Language Result Execution time Memory
805785 2023-08-03T23:27:26 Z ashcomp LOSTIKS (INOI20_lostiks) C++14
0 / 100
210 ms 174624 KB
#include <bits/stdc++.h>
 
using namespace std;
 
#define all(x) x.begin() , x.end()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define F first
#define S second
#define wall cerr<<"------------------------"<<endl
 
typedef long long ll;
 
const ll INF = 1e9;
const ll maxn = 1e6 + 10;
const ll mod = 1e9 + 7;
 
int n , m , k , ST , EN;
int h[maxn] , p[maxn] , st[maxn] , en[maxn];
int a[maxn<<1] , rmq[maxn<<1][21] , ps_rmq[maxn<<1][21] , rrmq[maxn<<1][21] , ps_rrmq[maxn<<1][21] , len[maxn<<1];
vector<int> g[maxn] , LSA;
bool mrk[maxn];
void DFS(int v)
{
        mrk[v] = 1;
        LSA.push_back(v);
        st[v] = LSA.size()-1;
        for(auto u : g[v]){
 
                if(mrk[u]==1)continue;
                p[u] = v;
                h[u] = h[v]+1;
                DFS(u);
                LSA.push_back(v);
        }
        en[v] = LSA.size()-1;
        
}
void pre_LCA()
{
        LSA.push_back(0);
        p[ST] = -1;
        h[ST] = 1;
        DFS(ST);
        m = LSA.size()-1;
        //wall;
        for(int i=1; i<=m; i++){
                a[i] = h[LSA[i]];
        }
        for(int j=0; j<21; j++){
                for(int i=1; i<=m; i++){
                        if(j==0){
                                rmq[i][j] = a[i];
                                rrmq[i][j] = a[i];
                                ps_rmq[i][j] = i;
                                ps_rrmq[i][j] = i;
                                continue;
                        }
                        if((i+(1<<j)-1)<=m){
                                rmq[i][j] = rmq[i][j-1];
                                ps_rmq[i][j] = ps_rmq[i][j-1];
                                if(rmq[i][j-1] > rmq[i+(1<<(j-1))][j-1]){
                                        rmq[i][j] = rmq[i+(1<<(j-1))][j-1];
                                        ps_rmq[i][j] = ps_rmq[i+(1<<(j-1))][j-1];
                                }
                        }
                        if((i-(1<<j)+1)>0){
                                rrmq[i][j] = rrmq[i][j-1];
                                ps_rrmq[i][j] = ps_rrmq[i][j-1];
                                if(rrmq[i][j-1] > rrmq[i-(1<<(j-1))][j-1]){
                                        rrmq[i][j] = rrmq[i-(1<<(j-1))][j-1];
                                        ps_rrmq[i][j] = ps_rrmq[i-(1<<(j-1))][j-1];
                                }
                        }
                }
        }
        int PS = 0;
        for(int i=1; i<=m; i++){
                if(((1<<PS)<<1)<=i){
                        PS++;
                }
                len[i] = PS;
        }
}//OK
int LCA(int v , int u)
{
        int l = min(st[v],st[u]) , r=max(st[v],st[u]);
        int ln = len[r-l+1];
        int x = rmq[l][ln] , y = rrmq[r][ln];
        if(x < y){
                int pos = ps_rmq[l][ln];
                return LSA[pos];
        }else{
                int pos = ps_rrmq[r][ln];
                return LSA[pos];
        }
}
int DIS(int v , int u)
{
        if(v==n+1 || u==n+1)return INF;
        return (h[v]+h[u]-h[LCA(v,u)]-h[LCA(v,u)]);
}
 
vector<pii> eg[maxn];
bool mark[maxn];
int req[maxn];
map<int,int> MP[maxn]; 
void dfs(int v)
{
        mark[v] = 1;
        for(auto e : eg[v]){
                int u=e.F , w=e.S;
                if(mark[u]==1)continue;
                p[u] = v;
                req[u] = req[v];
                if(w!=0){
                        int x = MP[v][u];
                        req[u] |= (1<<x);
                }
                dfs(u);
        }
}
 
vector<pair<int,pii>> EG;
pii dp[1<<21];
 
int main()
{
        ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
        cin>>n>>ST>>EN;
        int ps = 0;
        for(int i=1; i<n; i++){
                int v,u,w; cin>>v>>u>>w;
                if(w!=0){
                        MP[v][u] = ps;
                        MP[u][v] = ps;
                        ps++;
                        EG.push_back({w,{v,u}});
                }
                eg[v].push_back({u,w});
                eg[u].push_back({v,w});
                g[v].push_back(u);
                g[u].push_back(v);
        }
        eg[EN].push_back({n+1,EN});
        eg[n+1].push_back({EN,EN});
        MP[EN][n+1] = ps;
        MP[EN][n+1] = ps;
        EG.push_back({EN,{EN,n+1}});
        ps++;
        /**/
        pre_LCA();
        for(int i=1; i<=n; i++){
                p[i] = -1;
        }
        dfs(ST);
        for(int i=1; i<(1<<(ps)); i++){
                int VAL=INF , END=INF;
                for(int j=0; j<(ps); j++){
                        int x = i ^ (1<<j);
                        if(x>=i)continue; 
                        int V=EG[j].S.F , U=EG[j].S.S , W=EG[j].F;
                        
                        if(req[W]!=(req[W]&x))continue;
                        if(req[V]!=(req[V]&x) && req[U]!=(req[U]&x))continue;
                        if(DIS(V,ST) > DIS(ST,U)){
                                swap(V,U);
                        }
                        if(x==0){
                                int D1 = DIS(ST,W) + DIS(V,W);
                                if(VAL>D1){
                                        VAL = D1;
                                        END = V;
                                }
                                continue;
                        }else{

                                int v = dp[x].S , w=dp[x].F;
                                if(v==INF)continue;
                                int D1 = w + DIS(v,W) + DIS(W,V);
                                if(VAL>D1){
                                        VAL = D1;
                                        END = V;
                                }

                                continue;
                        }
                }
                dp[i] = {VAL,END};
        }
        // for(int i=1; i<(1<<ps); i++){
        //         for(int j=0; j<ps; j++){
        //                 cout<<((i>>j)&1);
        //         }cout<<" : "<<dp[i].F<<" , "<<dp[i].S<<"\n";
        // }
        int ans = INF;
        for(int i=1; i<(1<<(ps)); i++)
        {
                int res = ps-1;
                int x = i | (1<<res);
                ans = min(dp[x].F,ans);
        }
        if(ans==INF){
                cout<<-1;
                return 0;
        }
        cout<<ans;
        return 0;
}
/*
3
1 3
1 2 3
1 3 2
ans = -1
*/
/*
10
1 10
1 2 0
2 3 0
3 4 0
4 5 2
2 6 4
2 7 0
7 8 5
8 9 6
9 10 0
ans = 19
*/
/**
4
1 4
1 2 0
1 3 2
3 4 1
ans = 4;
*/
/*
5
3 1
1 2 5
2 3 4
3 4 0
4 5 2
ans = 10;
*/
# Verdict Execution time Memory Grader output
1 Correct 45 ms 94280 KB Output is correct
2 Correct 39 ms 94240 KB Output is correct
3 Correct 172 ms 172168 KB Output is correct
4 Correct 171 ms 171964 KB Output is correct
5 Correct 210 ms 171892 KB Output is correct
6 Correct 174 ms 171856 KB Output is correct
7 Correct 174 ms 172116 KB Output is correct
8 Correct 180 ms 172020 KB Output is correct
9 Correct 184 ms 172424 KB Output is correct
10 Correct 177 ms 172100 KB Output is correct
11 Correct 174 ms 172096 KB Output is correct
12 Correct 169 ms 174624 KB Output is correct
13 Incorrect 168 ms 173960 KB Output isn't correct
14 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 38 ms 94260 KB Output is correct
2 Correct 39 ms 94252 KB Output is correct
3 Correct 39 ms 94496 KB Output is correct
4 Correct 41 ms 94412 KB Output is correct
5 Incorrect 171 ms 108036 KB Output isn't correct
6 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 45 ms 94280 KB Output is correct
2 Correct 39 ms 94240 KB Output is correct
3 Correct 172 ms 172168 KB Output is correct
4 Correct 171 ms 171964 KB Output is correct
5 Correct 210 ms 171892 KB Output is correct
6 Correct 174 ms 171856 KB Output is correct
7 Correct 174 ms 172116 KB Output is correct
8 Correct 180 ms 172020 KB Output is correct
9 Correct 184 ms 172424 KB Output is correct
10 Correct 177 ms 172100 KB Output is correct
11 Correct 174 ms 172096 KB Output is correct
12 Correct 169 ms 174624 KB Output is correct
13 Incorrect 168 ms 173960 KB Output isn't correct
14 Halted 0 ms 0 KB -