oj.uz

Submission #806749

# Submission time Handle Problem Language Result Execution time Memory
806749 2023-08-04T09:33:20 Z ashcomp LOSTIKS (INOI20_lostiks) C++14
23 / 100
 2000 ms 279764 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<<1] , par[maxn<<1][22] , len[maxn<<1];
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<21; 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=20; 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 77 ms 188172 KB Output is correct
2 Correct 81 ms 188176 KB Output is correct
3 Correct 144 ms 206448 KB Output is correct
4 Correct 165 ms 206404 KB Output is correct
5 Correct 169 ms 206568 KB Output is correct
6 Correct 145 ms 206496 KB Output is correct
7 Correct 141 ms 206624 KB Output is correct
8 Correct 145 ms 206720 KB Output is correct
9 Correct 148 ms 206924 KB Output is correct
10 Correct 142 ms 206600 KB Output is correct
11 Correct 157 ms 206564 KB Output is correct
12 Correct 141 ms 209272 KB Output is correct
13 Correct 142 ms 208484 KB Output is correct
14 Correct 141 ms 207892 KB Output is correct
15 Correct 146 ms 209408 KB Output is correct
16 Correct 145 ms 210508 KB Output is correct
17 Correct 145 ms 210580 KB Output is correct
18 Correct 139 ms 211280 KB Output is correct
19 Correct 163 ms 217732 KB Output is correct
20 Correct 148 ms 217620 KB Output is correct
21 Correct 156 ms 217152 KB Output is correct
22 Correct 80 ms 188224 KB Output is correct
23 Correct 79 ms 188248 KB Output is correct
24 Correct 80 ms 188308 KB Output is correct
25 Correct 86 ms 188532 KB Output is correct
26 Correct 81 ms 188264 KB Output is correct

Subtask #2
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 188248 KB Output is correct
2 Correct 81 ms 188224 KB Output is correct
3 Correct 85 ms 188360 KB Output is correct
4 Correct 90 ms 188384 KB Output is correct
5 Execution timed out 2080 ms 279764 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 188172 KB Output is correct
2 Correct 81 ms 188176 KB Output is correct
3 Correct 144 ms 206448 KB Output is correct
4 Correct 165 ms 206404 KB Output is correct
5 Correct 169 ms 206568 KB Output is correct
6 Correct 145 ms 206496 KB Output is correct
7 Correct 141 ms 206624 KB Output is correct
8 Correct 145 ms 206720 KB Output is correct
9 Correct 148 ms 206924 KB Output is correct
10 Correct 142 ms 206600 KB Output is correct
11 Correct 157 ms 206564 KB Output is correct
12 Correct 141 ms 209272 KB Output is correct
13 Correct 142 ms 208484 KB Output is correct
14 Correct 141 ms 207892 KB Output is correct
15 Correct 146 ms 209408 KB Output is correct
16 Correct 145 ms 210508 KB Output is correct
17 Correct 145 ms 210580 KB Output is correct
18 Correct 139 ms 211280 KB Output is correct
19 Correct 163 ms 217732 KB Output is correct
20 Correct 148 ms 217620 KB Output is correct
21 Correct 156 ms 217152 KB Output is correct
22 Correct 80 ms 188224 KB Output is correct
23 Correct 79 ms 188248 KB Output is correct
24 Correct 80 ms 188308 KB Output is correct
25 Correct 86 ms 188532 KB Output is correct
26 Correct 81 ms 188264 KB Output is correct
27 Correct 88 ms 188248 KB Output is correct
28 Correct 81 ms 188224 KB Output is correct
29 Correct 85 ms 188360 KB Output is correct
30 Correct 90 ms 188384 KB Output is correct
31 Execution timed out 2080 ms 279764 KB Time limit exceeded
32 Halted 0 ms 0 KB -