oj.uz

Submission #805749

# Submission time Handle Problem Language Result Execution time Memory
805749 2023-08-03T22:29:58 Z ashcomp LOSTIKS (INOI20_lostiks) C++14
23 / 100
 2000 ms 186080 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<<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);
        }
        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++)
        {
                int res = EG.size()-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 45 ms 94256 KB Output is correct
2 Correct 40 ms 94356 KB Output is correct
3 Correct 178 ms 171896 KB Output is correct
4 Correct 172 ms 171860 KB Output is correct
5 Correct 176 ms 171968 KB Output is correct
6 Correct 174 ms 171928 KB Output is correct
7 Correct 171 ms 172096 KB Output is correct
8 Correct 176 ms 172104 KB Output is correct
9 Correct 186 ms 172564 KB Output is correct
10 Correct 178 ms 172132 KB Output is correct
11 Correct 178 ms 172092 KB Output is correct
12 Correct 163 ms 174528 KB Output is correct
13 Correct 165 ms 173912 KB Output is correct
14 Correct 167 ms 173352 KB Output is correct
15 Correct 166 ms 174792 KB Output is correct
16 Correct 188 ms 175968 KB Output is correct
17 Correct 167 ms 175976 KB Output is correct
18 Correct 169 ms 176824 KB Output is correct
19 Correct 169 ms 183268 KB Output is correct
20 Correct 183 ms 183104 KB Output is correct
21 Correct 166 ms 182624 KB Output is correct
22 Correct 40 ms 94512 KB Output is correct
23 Correct 41 ms 94412 KB Output is correct
24 Correct 40 ms 94496 KB Output is correct
25 Correct 40 ms 94548 KB Output is correct
26 Correct 40 ms 94436 KB Output is correct

Subtask #2
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 94340 KB Output is correct
2 Correct 40 ms 94292 KB Output is correct
3 Correct 43 ms 94556 KB Output is correct
4 Correct 43 ms 94668 KB Output is correct
5 Correct 1967 ms 186052 KB Output is correct
6 Correct 1448 ms 186080 KB Output is correct
7 Execution timed out 2077 ms 174616 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 94256 KB Output is correct
2 Correct 40 ms 94356 KB Output is correct
3 Correct 178 ms 171896 KB Output is correct
4 Correct 172 ms 171860 KB Output is correct
5 Correct 176 ms 171968 KB Output is correct
6 Correct 174 ms 171928 KB Output is correct
7 Correct 171 ms 172096 KB Output is correct
8 Correct 176 ms 172104 KB Output is correct
9 Correct 186 ms 172564 KB Output is correct
10 Correct 178 ms 172132 KB Output is correct
11 Correct 178 ms 172092 KB Output is correct
12 Correct 163 ms 174528 KB Output is correct
13 Correct 165 ms 173912 KB Output is correct
14 Correct 167 ms 173352 KB Output is correct
15 Correct 166 ms 174792 KB Output is correct
16 Correct 188 ms 175968 KB Output is correct
17 Correct 167 ms 175976 KB Output is correct
18 Correct 169 ms 176824 KB Output is correct
19 Correct 169 ms 183268 KB Output is correct
20 Correct 183 ms 183104 KB Output is correct
21 Correct 166 ms 182624 KB Output is correct
22 Correct 40 ms 94512 KB Output is correct
23 Correct 41 ms 94412 KB Output is correct
24 Correct 40 ms 94496 KB Output is correct
25 Correct 40 ms 94548 KB Output is correct
26 Correct 40 ms 94436 KB Output is correct
27 Correct 41 ms 94340 KB Output is correct
28 Correct 40 ms 94292 KB Output is correct
29 Correct 43 ms 94556 KB Output is correct
30 Correct 43 ms 94668 KB Output is correct
31 Correct 1967 ms 186052 KB Output is correct
32 Correct 1448 ms 186080 KB Output is correct
33 Execution timed out 2077 ms 174616 KB Time limit exceeded
34 Halted 0 ms 0 KB -