oj.uz

Submission #806676

# Submission time Handle Problem Language Result Execution time Memory
806676 2023-08-04T08:45:17 Z ashcomp LOSTIKS (INOI20_lostiks) C++14
0 / 100
 2000 ms 184636 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)
{
        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;
int dp[1<<21][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);
        }
        /**/
        pre_LCA();
        for(int i=1; i<=n; i++){
                p[i] = -1;
        }
        dfs(ST);
        for(int i=1; i<(1<<((int)EG.size())); i++){
                for(int j=0; j<((int)EG.size()); j++){
                        dp[i][j] = INF;
                }
        }
        for(int i=1; i<(1<<((int)EG.size())); i++){
                int pos = i;
                while(pos>0){
                        int j = __builtin_ctz(pos);
                        pos -= (1<<j);
                        int x = i^(1<<j);
                        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(x==0){
                                dp[i][j] = DIS(ST,W) + min(DIS(W,V),DIS(W,U));
                                continue;
                        }
                        int POS=i;
                        while(POS>0){
                                int f = __builtin_ctz(POS);
                                POS -= 1<<f;
                                int v=EG[f].S.F , u=EG[f].S.S;
                                int D1=DIS(ST,v) , D2=DIS(ST,u);
                                if(D1>D2){
                                        swap(v,u);
                                }
                                dp[i][j] = min(dp[i][j] , dp[x][f]+DIS(v,W)+min(DIS(W,V),DIS(W,U)) );
                        }
                }
        }
        // for(int i=1; i<(1<<((int)EG.size())); i++){
        //         int pos = i;
        //         while(pos>0){
        //                 int j = __builtin_ctz(pos);
        //                 pos -= (1<<j);
        //                 for(int f=0; f<(int)EG.size(); f++){
        //                         cout<<((i>>f)&1);
        //                 }cout<<" , "<<j<<" : "<<dp[i][j]<<"\n";
        //         }wall;
        // }
        ll ans = INF;
        for(int i=1; i<(1<<((int)EG.size())); i++)
        {
                for(int j=0; j<((int)EG.size()); j++){
                        int V=EG[j].S.F , U=EG[j].S.S;
                        if(DIS(V,ST)>DIS(U,ST)){
                                swap(V,U);
                        }
                        if(req[EN]!=(req[EN]&i))continue;
                        ans = min(ans , (ll)dp[i][j] + DIS(V,EN));
                }
        }
        if(ans==INF){
                cout<<-1;
                return 0;
        }
        cout<<ans;
        return 0;
}
/*
3
1 3
1 2 3
1 3 2
*/
/*
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 = 15
*/
/**
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;
*/

Subtask #1
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 94312 KB Output is correct
2 Correct 40 ms 94284 KB Output is correct
3 Correct 173 ms 173280 KB Output is correct
4 Correct 176 ms 173268 KB Output is correct
5 Correct 175 ms 173372 KB Output is correct
6 Correct 167 ms 173244 KB Output is correct
7 Correct 171 ms 173372 KB Output is correct
8 Correct 171 ms 173372 KB Output is correct
9 Correct 174 ms 173868 KB Output is correct
10 Correct 197 ms 173440 KB Output is correct
11 Correct 171 ms 173400 KB Output is correct
12 Correct 164 ms 175908 KB Output is correct
13 Correct 167 ms 175244 KB Output is correct
14 Correct 167 ms 174576 KB Output is correct
15 Correct 170 ms 176180 KB Output is correct
16 Correct 169 ms 177276 KB Output is correct
17 Correct 164 ms 177304 KB Output is correct
18 Correct 171 ms 178060 KB Output is correct
19 Correct 164 ms 184636 KB Output is correct
20 Correct 168 ms 184356 KB Output is correct
21 Correct 167 ms 183988 KB Output is correct
22 Correct 40 ms 94408 KB Output is correct
23 Correct 41 ms 94488 KB Output is correct
24 Correct 40 ms 94460 KB Output is correct
25 Correct 42 ms 94464 KB Output is correct
26 Incorrect 45 ms 94468 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #2
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 94240 KB Output is correct
2 Correct 41 ms 94332 KB Output is correct
3 Correct 44 ms 94496 KB Output is correct
4 Correct 42 ms 94560 KB Output is correct
5 Correct 737 ms 143004 KB Output is correct
6 Correct 548 ms 143012 KB Output is correct
7 Correct 831 ms 142912 KB Output is correct
8 Correct 586 ms 143000 KB Output is correct
9 Correct 699 ms 143016 KB Output is correct
10 Correct 352 ms 142944 KB Output is correct
11 Correct 350 ms 143044 KB Output is correct
12 Correct 355 ms 143036 KB Output is correct
13 Correct 349 ms 143036 KB Output is correct
14 Correct 363 ms 143044 KB Output is correct
15 Correct 644 ms 143036 KB Output is correct
16 Correct 815 ms 143048 KB Output is correct
17 Correct 664 ms 143024 KB Output is correct
18 Correct 367 ms 143264 KB Output is correct
19 Correct 408 ms 143264 KB Output is correct
20 Correct 360 ms 143272 KB Output is correct
21 Correct 358 ms 143340 KB Output is correct
22 Correct 345 ms 143704 KB Output is correct
23 Correct 363 ms 143796 KB Output is correct
24 Correct 349 ms 143816 KB Output is correct
25 Execution timed out 2094 ms 180520 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #3
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 94312 KB Output is correct
2 Correct 40 ms 94284 KB Output is correct
3 Correct 173 ms 173280 KB Output is correct
4 Correct 176 ms 173268 KB Output is correct
5 Correct 175 ms 173372 KB Output is correct
6 Correct 167 ms 173244 KB Output is correct
7 Correct 171 ms 173372 KB Output is correct
8 Correct 171 ms 173372 KB Output is correct
9 Correct 174 ms 173868 KB Output is correct
10 Correct 197 ms 173440 KB Output is correct
11 Correct 171 ms 173400 KB Output is correct
12 Correct 164 ms 175908 KB Output is correct
13 Correct 167 ms 175244 KB Output is correct
14 Correct 167 ms 174576 KB Output is correct
15 Correct 170 ms 176180 KB Output is correct
16 Correct 169 ms 177276 KB Output is correct
17 Correct 164 ms 177304 KB Output is correct
18 Correct 171 ms 178060 KB Output is correct
19 Correct 164 ms 184636 KB Output is correct
20 Correct 168 ms 184356 KB Output is correct
21 Correct 167 ms 183988 KB Output is correct
22 Correct 40 ms 94408 KB Output is correct
23 Correct 41 ms 94488 KB Output is correct
24 Correct 40 ms 94460 KB Output is correct
25 Correct 42 ms 94464 KB Output is correct
26 Incorrect 45 ms 94468 KB Output isn't correct
27 Halted 0 ms 0 KB -