oj.uz

Submission #806578

# Submission time Handle Problem Language Result Execution time Memory
806578 2023-08-04T08:06:52 Z ashcomp LOSTIKS (INOI20_lostiks) C++17
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++){
                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));
                                //cout<<i<<","<<j<<" \\ "<<V<<","<<U<<","<<W<<" : "<<DIS(ST,W) <<" , "<< DIS(W,V) <<" , "<<DIS(W,U)<<"\n";
                                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;
                        if(DIS(V,ST)>DIS(U,ST)){
                                swap(V,U);
                        }
                        if(req[EN]!=(req[EN]&i))continue;
                        ans = min(ans , 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 38 ms 94352 KB Output is correct
2 Correct 43 ms 94264 KB Output is correct
3 Correct 175 ms 173220 KB Output is correct
4 Correct 181 ms 173320 KB Output is correct
5 Correct 187 ms 173368 KB Output is correct
6 Correct 194 ms 173288 KB Output is correct
7 Correct 204 ms 173452 KB Output is correct
8 Correct 187 ms 173464 KB Output is correct
9 Correct 198 ms 173752 KB Output is correct
10 Correct 198 ms 173444 KB Output is correct
11 Correct 195 ms 173460 KB Output is correct
12 Correct 204 ms 175892 KB Output is correct
13 Correct 170 ms 175240 KB Output is correct
14 Correct 174 ms 174572 KB Output is correct
15 Correct 173 ms 176112 KB Output is correct
16 Correct 182 ms 177328 KB Output is correct
17 Correct 189 ms 177388 KB Output is correct
18 Correct 184 ms 178172 KB Output is correct
19 Correct 175 ms 184636 KB Output is correct
20 Correct 181 ms 184352 KB Output is correct
21 Correct 203 ms 183992 KB Output is correct
22 Correct 44 ms 94392 KB Output is correct
23 Correct 46 ms 94488 KB Output is correct
24 Correct 45 ms 94452 KB Output is correct
25 Correct 45 ms 94464 KB Output is correct
26 Incorrect 45 ms 94508 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #2
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 94264 KB Output is correct
2 Correct 42 ms 94348 KB Output is correct
3 Correct 43 ms 94548 KB Output is correct
4 Correct 55 ms 94528 KB Output is correct
5 Correct 1121 ms 143004 KB Output is correct
6 Correct 785 ms 143008 KB Output is correct
7 Correct 1275 ms 143004 KB Output is correct
8 Correct 881 ms 143008 KB Output is correct
9 Correct 1016 ms 143008 KB Output is correct
10 Correct 505 ms 143032 KB Output is correct
11 Correct 510 ms 143044 KB Output is correct
12 Correct 543 ms 143040 KB Output is correct
13 Correct 507 ms 143032 KB Output is correct
14 Correct 568 ms 143044 KB Output is correct
15 Correct 905 ms 143028 KB Output is correct
16 Correct 1236 ms 143052 KB Output is correct
17 Correct 968 ms 143036 KB Output is correct
18 Correct 504 ms 143216 KB Output is correct
19 Correct 498 ms 143268 KB Output is correct
20 Correct 509 ms 143276 KB Output is correct
21 Correct 493 ms 143464 KB Output is correct
22 Correct 512 ms 143804 KB Output is correct
23 Correct 488 ms 143700 KB Output is correct
24 Correct 482 ms 143812 KB Output is correct
25 Execution timed out 2076 ms 180428 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #3
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 94352 KB Output is correct
2 Correct 43 ms 94264 KB Output is correct
3 Correct 175 ms 173220 KB Output is correct
4 Correct 181 ms 173320 KB Output is correct
5 Correct 187 ms 173368 KB Output is correct
6 Correct 194 ms 173288 KB Output is correct
7 Correct 204 ms 173452 KB Output is correct
8 Correct 187 ms 173464 KB Output is correct
9 Correct 198 ms 173752 KB Output is correct
10 Correct 198 ms 173444 KB Output is correct
11 Correct 195 ms 173460 KB Output is correct
12 Correct 204 ms 175892 KB Output is correct
13 Correct 170 ms 175240 KB Output is correct
14 Correct 174 ms 174572 KB Output is correct
15 Correct 173 ms 176112 KB Output is correct
16 Correct 182 ms 177328 KB Output is correct
17 Correct 189 ms 177388 KB Output is correct
18 Correct 184 ms 178172 KB Output is correct
19 Correct 175 ms 184636 KB Output is correct
20 Correct 181 ms 184352 KB Output is correct
21 Correct 203 ms 183992 KB Output is correct
22 Correct 44 ms 94392 KB Output is correct
23 Correct 46 ms 94488 KB Output is correct
24 Correct 45 ms 94452 KB Output is correct
25 Correct 45 ms 94464 KB Output is correct
26 Incorrect 45 ms 94508 KB Output isn't correct
27 Halted 0 ms 0 KB -