oj.uz

Submission #806756

# Submission time Handle Problem Language Result Execution time Memory
806756 2023-08-04T09:35:42 Z ashcomp LOSTIKS (INOI20_lostiks) C++14
23 / 100
 2000 ms 279856 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 , ti;
int h[maxn] , p[maxn] , st[maxn] , en[maxn];
int a[maxn] , par[maxn][25];
vector<int> g[maxn] , LSA;
bool mrk[maxn];
void DFS(int v)
{
        mrk[v] = 1;
        st[v] = ti++;
        for(auto u : g[v]){
                if(mrk[u]==1)continue;
                p[u] = v;
                h[u] = h[v]+1;
                DFS(u);
        }
        en[v] = ti++;
}
inline void pre_LCA()
{
        p[ST] = ST;
        DFS(ST);
        for(int j=0; j<25; j++){
                for(int i=1; i<=n; i++){
                        if(j==0){
                                par[i][j] = p[i];
                                continue;
                        }else{
                                int x = par[i][j-1];
                                par[i][j] = par[x][j-1];
                        }
                }
        }
}//OK
inline int LCA(int v , int u)
{
        if(st[v]<=st[u]&&en[u]<=en[v])return v;
        if(st[u]<=st[v]&&en[v]<=en[u])return u;
        for(int i=24; i>=0; i--){
                int x = par[v][i];
                if(st[x]>=st[u] || en[u]>=en[x]){
                        v = x;
                }
        }
        v = p[v];
        return v;
}
inline 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(ll 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(ll 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 = 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;
*/

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 188208 KB Output is correct
2 Correct 78 ms 188220 KB Output is correct
3 Correct 139 ms 207348 KB Output is correct
4 Correct 142 ms 207420 KB Output is correct
5 Correct 138 ms 207468 KB Output is correct
6 Correct 143 ms 207376 KB Output is correct
7 Correct 149 ms 207600 KB Output is correct
8 Correct 142 ms 207516 KB Output is correct
9 Correct 142 ms 207812 KB Output is correct
10 Correct 146 ms 207468 KB Output is correct
11 Correct 150 ms 207548 KB Output is correct
12 Correct 143 ms 210012 KB Output is correct
13 Correct 139 ms 209400 KB Output is correct
14 Correct 139 ms 208792 KB Output is correct
15 Correct 153 ms 210392 KB Output is correct
16 Correct 140 ms 211468 KB Output is correct
17 Correct 140 ms 211440 KB Output is correct
18 Correct 138 ms 212288 KB Output is correct
19 Correct 144 ms 218760 KB Output is correct
20 Correct 141 ms 218444 KB Output is correct
21 Correct 142 ms 218024 KB Output is correct
22 Correct 79 ms 188292 KB Output is correct
23 Correct 79 ms 188196 KB Output is correct
24 Correct 86 ms 188368 KB Output is correct
25 Correct 79 ms 188236 KB Output is correct
26 Correct 79 ms 188220 KB Output is correct

Subtask #2
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 188160 KB Output is correct
2 Correct 77 ms 188236 KB Output is correct
3 Correct 84 ms 188412 KB Output is correct
4 Correct 85 ms 188412 KB Output is correct
5 Execution timed out 2092 ms 279856 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 188208 KB Output is correct
2 Correct 78 ms 188220 KB Output is correct
3 Correct 139 ms 207348 KB Output is correct
4 Correct 142 ms 207420 KB Output is correct
5 Correct 138 ms 207468 KB Output is correct
6 Correct 143 ms 207376 KB Output is correct
7 Correct 149 ms 207600 KB Output is correct
8 Correct 142 ms 207516 KB Output is correct
9 Correct 142 ms 207812 KB Output is correct
10 Correct 146 ms 207468 KB Output is correct
11 Correct 150 ms 207548 KB Output is correct
12 Correct 143 ms 210012 KB Output is correct
13 Correct 139 ms 209400 KB Output is correct
14 Correct 139 ms 208792 KB Output is correct
15 Correct 153 ms 210392 KB Output is correct
16 Correct 140 ms 211468 KB Output is correct
17 Correct 140 ms 211440 KB Output is correct
18 Correct 138 ms 212288 KB Output is correct
19 Correct 144 ms 218760 KB Output is correct
20 Correct 141 ms 218444 KB Output is correct
21 Correct 142 ms 218024 KB Output is correct
22 Correct 79 ms 188292 KB Output is correct
23 Correct 79 ms 188196 KB Output is correct
24 Correct 86 ms 188368 KB Output is correct
25 Correct 79 ms 188236 KB Output is correct
26 Correct 79 ms 188220 KB Output is correct
27 Correct 79 ms 188160 KB Output is correct
28 Correct 77 ms 188236 KB Output is correct
29 Correct 84 ms 188412 KB Output is correct
30 Correct 85 ms 188412 KB Output is correct
31 Execution timed out 2092 ms 279856 KB Time limit exceeded
32 Halted 0 ms 0 KB -