oj.uz

Submission #805761

# Submission time Handle Problem Language Result Execution time Memory
805761 2023-08-03T22:47:11 Z ashcomp LOSTIKS (INOI20_lostiks) C++14
23 / 100
 2000 ms 190136 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<<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);
        }
        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));
                                //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++)
        {
                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 43 ms 94268 KB Output is correct
2 Correct 43 ms 94268 KB Output is correct
3 Correct 177 ms 171876 KB Output is correct
4 Correct 202 ms 171968 KB Output is correct
5 Correct 174 ms 172008 KB Output is correct
6 Correct 177 ms 171872 KB Output is correct
7 Correct 181 ms 172180 KB Output is correct
8 Correct 177 ms 172052 KB Output is correct
9 Correct 179 ms 172396 KB Output is correct
10 Correct 175 ms 172040 KB Output is correct
11 Correct 188 ms 172032 KB Output is correct
12 Correct 167 ms 174552 KB Output is correct
13 Correct 166 ms 173904 KB Output is correct
14 Correct 167 ms 173224 KB Output is correct
15 Correct 169 ms 174780 KB Output is correct
16 Correct 166 ms 175936 KB Output is correct
17 Correct 165 ms 176072 KB Output is correct
18 Correct 185 ms 176836 KB Output is correct
19 Correct 176 ms 183228 KB Output is correct
20 Correct 207 ms 183268 KB Output is correct
21 Correct 200 ms 182916 KB Output is correct
22 Correct 49 ms 94512 KB Output is correct
23 Correct 48 ms 94528 KB Output is correct
24 Correct 49 ms 94400 KB Output is correct
25 Correct 48 ms 94488 KB Output is correct
26 Correct 48 ms 94504 KB Output is correct

Subtask #2
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 94256 KB Output is correct
2 Correct 48 ms 94236 KB Output is correct
3 Correct 52 ms 94820 KB Output is correct
4 Correct 51 ms 94604 KB Output is correct
5 Correct 1996 ms 190136 KB Output is correct
6 Correct 1394 ms 190100 KB Output is correct
7 Execution timed out 2080 ms 176008 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 94268 KB Output is correct
2 Correct 43 ms 94268 KB Output is correct
3 Correct 177 ms 171876 KB Output is correct
4 Correct 202 ms 171968 KB Output is correct
5 Correct 174 ms 172008 KB Output is correct
6 Correct 177 ms 171872 KB Output is correct
7 Correct 181 ms 172180 KB Output is correct
8 Correct 177 ms 172052 KB Output is correct
9 Correct 179 ms 172396 KB Output is correct
10 Correct 175 ms 172040 KB Output is correct
11 Correct 188 ms 172032 KB Output is correct
12 Correct 167 ms 174552 KB Output is correct
13 Correct 166 ms 173904 KB Output is correct
14 Correct 167 ms 173224 KB Output is correct
15 Correct 169 ms 174780 KB Output is correct
16 Correct 166 ms 175936 KB Output is correct
17 Correct 165 ms 176072 KB Output is correct
18 Correct 185 ms 176836 KB Output is correct
19 Correct 176 ms 183228 KB Output is correct
20 Correct 207 ms 183268 KB Output is correct
21 Correct 200 ms 182916 KB Output is correct
22 Correct 49 ms 94512 KB Output is correct
23 Correct 48 ms 94528 KB Output is correct
24 Correct 49 ms 94400 KB Output is correct
25 Correct 48 ms 94488 KB Output is correct
26 Correct 48 ms 94504 KB Output is correct
27 Correct 48 ms 94256 KB Output is correct
28 Correct 48 ms 94236 KB Output is correct
29 Correct 52 ms 94820 KB Output is correct
30 Correct 51 ms 94604 KB Output is correct
31 Correct 1996 ms 190136 KB Output is correct
32 Correct 1394 ms 190100 KB Output is correct
33 Execution timed out 2080 ms 176008 KB Time limit exceeded
34 Halted 0 ms 0 KB -