oj.uz

Submission #805766

# Submission time Handle Problem Language Result Execution time Memory
805766 2023-08-03T22:55:37 Z ashcomp LOSTIKS (INOI20_lostiks) C++14
23 / 100
 2000 ms 190132 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;

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

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);
        }
}
 
pair<int,pii> EG[22];
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;
                        EG[ps]={w,{v,u}};
                        ps++;
                        
                }
                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[ps]={EN,{EN,n+1}};
        ps++;
        /**/
        pre_LCA();
        for(int i=1; i<=n; i++){
                p[i] = -1;
        }
        dfs(ST);
        for(int i=1; i<(1<<(ps)); i++){
                for(int j=0; j<(ps); j++){
                        dp[i][j] = INF;
                }
                       
                for(int j=0; j<(ps); j++){
                        int x = i ^ (1<<j);
                        if(x>i)continue; 
                        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;
                        }
                        for(int f=0; f<(ps); f++){
                                int v=EG[f].S.F , u=EG[f].S.S;
                                if(DIS(ST,v)>DIS(ST,u)){
                                        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; i<(1<<(ps)); i++)
        {
                int res = ps-1;
                ans = min(dp[i][res],ans);
        }
        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 43 ms 94292 KB Output is correct
2 Correct 47 ms 94248 KB Output is correct
3 Correct 179 ms 171864 KB Output is correct
4 Correct 221 ms 171968 KB Output is correct
5 Correct 185 ms 171988 KB Output is correct
6 Correct 179 ms 171980 KB Output is correct
7 Correct 182 ms 172096 KB Output is correct
8 Correct 190 ms 172084 KB Output is correct
9 Correct 181 ms 172348 KB Output is correct
10 Correct 183 ms 172100 KB Output is correct
11 Correct 191 ms 172064 KB Output is correct
12 Correct 194 ms 174624 KB Output is correct
13 Correct 190 ms 173988 KB Output is correct
14 Correct 180 ms 173332 KB Output is correct
15 Correct 170 ms 174792 KB Output is correct
16 Correct 193 ms 175924 KB Output is correct
17 Correct 184 ms 176248 KB Output is correct
18 Correct 170 ms 176816 KB Output is correct
19 Correct 193 ms 183292 KB Output is correct
20 Correct 180 ms 183040 KB Output is correct
21 Correct 176 ms 182588 KB Output is correct
22 Correct 47 ms 94504 KB Output is correct
23 Correct 47 ms 94420 KB Output is correct
24 Correct 46 ms 94500 KB Output is correct
25 Correct 47 ms 94460 KB Output is correct
26 Correct 48 ms 94492 KB Output is correct

Subtask #2
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 94284 KB Output is correct
2 Correct 46 ms 94324 KB Output is correct
3 Correct 48 ms 94644 KB Output is correct
4 Correct 48 ms 94616 KB Output is correct
5 Correct 1954 ms 190132 KB Output is correct
6 Correct 1405 ms 190088 KB Output is correct
7 Execution timed out 2081 ms 175328 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 94292 KB Output is correct
2 Correct 47 ms 94248 KB Output is correct
3 Correct 179 ms 171864 KB Output is correct
4 Correct 221 ms 171968 KB Output is correct
5 Correct 185 ms 171988 KB Output is correct
6 Correct 179 ms 171980 KB Output is correct
7 Correct 182 ms 172096 KB Output is correct
8 Correct 190 ms 172084 KB Output is correct
9 Correct 181 ms 172348 KB Output is correct
10 Correct 183 ms 172100 KB Output is correct
11 Correct 191 ms 172064 KB Output is correct
12 Correct 194 ms 174624 KB Output is correct
13 Correct 190 ms 173988 KB Output is correct
14 Correct 180 ms 173332 KB Output is correct
15 Correct 170 ms 174792 KB Output is correct
16 Correct 193 ms 175924 KB Output is correct
17 Correct 184 ms 176248 KB Output is correct
18 Correct 170 ms 176816 KB Output is correct
19 Correct 193 ms 183292 KB Output is correct
20 Correct 180 ms 183040 KB Output is correct
21 Correct 176 ms 182588 KB Output is correct
22 Correct 47 ms 94504 KB Output is correct
23 Correct 47 ms 94420 KB Output is correct
24 Correct 46 ms 94500 KB Output is correct
25 Correct 47 ms 94460 KB Output is correct
26 Correct 48 ms 94492 KB Output is correct
27 Correct 51 ms 94284 KB Output is correct
28 Correct 46 ms 94324 KB Output is correct
29 Correct 48 ms 94644 KB Output is correct
30 Correct 48 ms 94616 KB Output is correct
31 Correct 1954 ms 190132 KB Output is correct
32 Correct 1405 ms 190088 KB Output is correct
33 Execution timed out 2081 ms 175328 KB Time limit exceeded
34 Halted 0 ms 0 KB -