oj.uz

Submission #806704

# Submission time Handle Problem Language Result Execution time Memory
806704 2023-08-04T09:03:53 Z ashcomp LOSTIKS (INOI20_lostiks) C++14
23 / 100
 2000 ms 368828 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 = 2e6 + 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][22] , ps_rmq[maxn<<1][22] , rrmq[maxn<<1][22] , ps_rrmq[maxn<<1][22] , 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<<22][22];
 
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()))+(1<<((int)EG.size())); i++){
                for(int j=0; j<((int)EG.size())+1; 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)) );
                        }
                }
        }
        /***********************************/
        ps = ((int)EG.size());
        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}});

        for(int i=(1<<ps); i<(1<<(ps+1)); i++){
                int j = ps;
                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)) );
                }
        }
        int ans = INF;
        for(int i=(1<<ps); i<(1<<(ps+1)); i++){
                ans = min(ans , dp[i][ps]);
        }
        /*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
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 188196 KB Output is correct
2 Correct 75 ms 188232 KB Output is correct
3 Correct 220 ms 268964 KB Output is correct
4 Correct 212 ms 268940 KB Output is correct
5 Correct 222 ms 269104 KB Output is correct
6 Correct 217 ms 268952 KB Output is correct
7 Correct 208 ms 269100 KB Output is correct
8 Correct 218 ms 269176 KB Output is correct
9 Correct 221 ms 269528 KB Output is correct
10 Correct 207 ms 269116 KB Output is correct
11 Correct 213 ms 269136 KB Output is correct
12 Correct 207 ms 271724 KB Output is correct
13 Correct 215 ms 271080 KB Output is correct
14 Correct 211 ms 270304 KB Output is correct
15 Correct 201 ms 271948 KB Output is correct
16 Correct 213 ms 273008 KB Output is correct
17 Correct 210 ms 273032 KB Output is correct
18 Correct 206 ms 273924 KB Output is correct
19 Correct 215 ms 280268 KB Output is correct
20 Correct 216 ms 280152 KB Output is correct
21 Correct 204 ms 279712 KB Output is correct
22 Correct 76 ms 188356 KB Output is correct
23 Correct 76 ms 188412 KB Output is correct
24 Correct 75 ms 188412 KB Output is correct
25 Correct 76 ms 188404 KB Output is correct
26 Correct 76 ms 188460 KB Output is correct

Subtask #2
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 188172 KB Output is correct
2 Correct 77 ms 188252 KB Output is correct
3 Correct 76 ms 188616 KB Output is correct
4 Correct 75 ms 188520 KB Output is correct
5 Correct 706 ms 284276 KB Output is correct
6 Correct 530 ms 284260 KB Output is correct
7 Correct 828 ms 284276 KB Output is correct
8 Correct 576 ms 284284 KB Output is correct
9 Correct 673 ms 284276 KB Output is correct
10 Correct 321 ms 284300 KB Output is correct
11 Correct 314 ms 284236 KB Output is correct
12 Correct 324 ms 284196 KB Output is correct
13 Correct 345 ms 284292 KB Output is correct
14 Correct 319 ms 284312 KB Output is correct
15 Correct 610 ms 284240 KB Output is correct
16 Correct 823 ms 284312 KB Output is correct
17 Correct 636 ms 284292 KB Output is correct
18 Correct 329 ms 284520 KB Output is correct
19 Correct 320 ms 284536 KB Output is correct
20 Correct 323 ms 284492 KB Output is correct
21 Correct 316 ms 284508 KB Output is correct
22 Correct 343 ms 285076 KB Output is correct
23 Correct 324 ms 285064 KB Output is correct
24 Correct 316 ms 285092 KB Output is correct
25 Execution timed out 2103 ms 368828 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #3
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 188196 KB Output is correct
2 Correct 75 ms 188232 KB Output is correct
3 Correct 220 ms 268964 KB Output is correct
4 Correct 212 ms 268940 KB Output is correct
5 Correct 222 ms 269104 KB Output is correct
6 Correct 217 ms 268952 KB Output is correct
7 Correct 208 ms 269100 KB Output is correct
8 Correct 218 ms 269176 KB Output is correct
9 Correct 221 ms 269528 KB Output is correct
10 Correct 207 ms 269116 KB Output is correct
11 Correct 213 ms 269136 KB Output is correct
12 Correct 207 ms 271724 KB Output is correct
13 Correct 215 ms 271080 KB Output is correct
14 Correct 211 ms 270304 KB Output is correct
15 Correct 201 ms 271948 KB Output is correct
16 Correct 213 ms 273008 KB Output is correct
17 Correct 210 ms 273032 KB Output is correct
18 Correct 206 ms 273924 KB Output is correct
19 Correct 215 ms 280268 KB Output is correct
20 Correct 216 ms 280152 KB Output is correct
21 Correct 204 ms 279712 KB Output is correct
22 Correct 76 ms 188356 KB Output is correct
23 Correct 76 ms 188412 KB Output is correct
24 Correct 75 ms 188412 KB Output is correct
25 Correct 76 ms 188404 KB Output is correct
26 Correct 76 ms 188460 KB Output is correct
27 Correct 77 ms 188172 KB Output is correct
28 Correct 77 ms 188252 KB Output is correct
29 Correct 76 ms 188616 KB Output is correct
30 Correct 75 ms 188520 KB Output is correct
31 Correct 706 ms 284276 KB Output is correct
32 Correct 530 ms 284260 KB Output is correct
33 Correct 828 ms 284276 KB Output is correct
34 Correct 576 ms 284284 KB Output is correct
35 Correct 673 ms 284276 KB Output is correct
36 Correct 321 ms 284300 KB Output is correct
37 Correct 314 ms 284236 KB Output is correct
38 Correct 324 ms 284196 KB Output is correct
39 Correct 345 ms 284292 KB Output is correct
40 Correct 319 ms 284312 KB Output is correct
41 Correct 610 ms 284240 KB Output is correct
42 Correct 823 ms 284312 KB Output is correct
43 Correct 636 ms 284292 KB Output is correct
44 Correct 329 ms 284520 KB Output is correct
45 Correct 320 ms 284536 KB Output is correct
46 Correct 323 ms 284492 KB Output is correct
47 Correct 316 ms 284508 KB Output is correct
48 Correct 343 ms 285076 KB Output is correct
49 Correct 324 ms 285064 KB Output is correct
50 Correct 316 ms 285092 KB Output is correct
51 Execution timed out 2103 ms 368828 KB Time limit exceeded
52 Halted 0 ms 0 KB -