oj.uz

Submission #805753

# Submission time Handle Problem Language Result Execution time Memory
805753 2023-08-03T22:36:57 Z ashcomp LOSTIKS (INOI20_lostiks) C++14
0 / 100
 2000 ms 183284 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
 
#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O2")

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)]);
}
//OK

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<<20][20];

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}});*/
        /**/
        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 j=0; j<((int)EG.size()); j++){
                        int V=EG[j].S.F , U=EG[j].S.S , W=EG[j].F;
                        int x = i ^ (1<<j);
                        if(x>i)continue;
                        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;
                        }
                        for(int f=0; f<((int)EG.size()); 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);
                                        swap(D1,D2);
                                }
                                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; 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;
                        int x = req[EN]|i;
                        ans = min(ans , dp[x][j] + min(DIS(V,EN),DIS(U,EN)));
                }
        }
        if(ans==INF){
                cout<<-1;
                return 0;
        }
        cout<<ans+1;
        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
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 94280 KB Output is correct
2 Correct 39 ms 94288 KB Output is correct
3 Correct 168 ms 171900 KB Output is correct
4 Correct 166 ms 171876 KB Output is correct
5 Correct 175 ms 171968 KB Output is correct
6 Correct 175 ms 171900 KB Output is correct
7 Correct 173 ms 172132 KB Output is correct
8 Correct 171 ms 172044 KB Output is correct
9 Correct 192 ms 172404 KB Output is correct
10 Correct 167 ms 172120 KB Output is correct
11 Correct 201 ms 172088 KB Output is correct
12 Correct 161 ms 174608 KB Output is correct
13 Correct 169 ms 173896 KB Output is correct
14 Correct 167 ms 173268 KB Output is correct
15 Correct 190 ms 174812 KB Output is correct
16 Correct 163 ms 175928 KB Output is correct
17 Correct 162 ms 176040 KB Output is correct
18 Correct 165 ms 176776 KB Output is correct
19 Correct 170 ms 183284 KB Output is correct
20 Correct 177 ms 183044 KB Output is correct
21 Correct 168 ms 182652 KB Output is correct
22 Correct 45 ms 94500 KB Output is correct
23 Correct 42 ms 94388 KB Output is correct
24 Correct 40 ms 94396 KB Output is correct
25 Correct 40 ms 94392 KB Output is correct
26 Incorrect 41 ms 94440 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #2
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 94232 KB Output is correct
2 Correct 40 ms 94240 KB Output is correct
3 Correct 40 ms 94480 KB Output is correct
4 Correct 45 ms 94484 KB Output is correct
5 Correct 1028 ms 140868 KB Output is correct
6 Correct 757 ms 140876 KB Output is correct
7 Correct 1272 ms 140916 KB Output is correct
8 Correct 922 ms 140908 KB Output is correct
9 Correct 1010 ms 140960 KB Output is correct
10 Correct 497 ms 140980 KB Output is correct
11 Correct 512 ms 140992 KB Output is correct
12 Correct 501 ms 140964 KB Output is correct
13 Correct 509 ms 140980 KB Output is correct
14 Correct 507 ms 140996 KB Output is correct
15 Correct 892 ms 140984 KB Output is correct
16 Correct 1141 ms 140892 KB Output is correct
17 Correct 940 ms 140864 KB Output is correct
18 Correct 552 ms 141416 KB Output is correct
19 Correct 522 ms 141212 KB Output is correct
20 Correct 602 ms 141228 KB Output is correct
21 Correct 578 ms 141184 KB Output is correct
22 Correct 494 ms 141636 KB Output is correct
23 Correct 522 ms 141644 KB Output is correct
24 Correct 532 ms 141760 KB Output is correct
25 Execution timed out 2089 ms 125620 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 94280 KB Output is correct
2 Correct 39 ms 94288 KB Output is correct
3 Correct 168 ms 171900 KB Output is correct
4 Correct 166 ms 171876 KB Output is correct
5 Correct 175 ms 171968 KB Output is correct
6 Correct 175 ms 171900 KB Output is correct
7 Correct 173 ms 172132 KB Output is correct
8 Correct 171 ms 172044 KB Output is correct
9 Correct 192 ms 172404 KB Output is correct
10 Correct 167 ms 172120 KB Output is correct
11 Correct 201 ms 172088 KB Output is correct
12 Correct 161 ms 174608 KB Output is correct
13 Correct 169 ms 173896 KB Output is correct
14 Correct 167 ms 173268 KB Output is correct
15 Correct 190 ms 174812 KB Output is correct
16 Correct 163 ms 175928 KB Output is correct
17 Correct 162 ms 176040 KB Output is correct
18 Correct 165 ms 176776 KB Output is correct
19 Correct 170 ms 183284 KB Output is correct
20 Correct 177 ms 183044 KB Output is correct
21 Correct 168 ms 182652 KB Output is correct
22 Correct 45 ms 94500 KB Output is correct
23 Correct 42 ms 94388 KB Output is correct
24 Correct 40 ms 94396 KB Output is correct
25 Correct 40 ms 94392 KB Output is correct
26 Incorrect 41 ms 94440 KB Output isn't correct
27 Halted 0 ms 0 KB -