oj.uz

Submission #805757

# Submission time Handle Problem Language Result Execution time Memory
805757 2023-08-03T22:44:22 Z ashcomp LOSTIKS (INOI20_lostiks) C++14
0 / 100
 2000 ms 183204 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(DIS(V,ST) > DIS(U,ST)){
                                swap(V,U);
                        }
                        if(x==0){
                                dp[i][j] = (DIS(ST,W) + DIS(W,V));
                                continue;
                        }
                        for(int f=0; f<((int)EG.size()); 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)+DIS(V,W));
                        }
                }
        }
        int ans = INF;
        for(int i=1; i<(1<<((int)EG.size())); i++){
                int x = req[EN]|i;
                if(x!=i)continue;
                for(int j=0; j<((int)EG.size()); j++){
                        int V=EG[j].S.F , U=EG[j].S.S;
                        int D1=DIS(ST,V) , D2=DIS(ST,U);
                        if(D1>D2){
                                swap(V,U);
                        }
                        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 = 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 39 ms 94284 KB Output is correct
2 Correct 39 ms 94240 KB Output is correct
3 Correct 164 ms 171836 KB Output is correct
4 Correct 186 ms 171868 KB Output is correct
5 Correct 169 ms 171900 KB Output is correct
6 Correct 186 ms 171932 KB Output is correct
7 Correct 174 ms 172052 KB Output is correct
8 Correct 177 ms 172112 KB Output is correct
9 Correct 193 ms 172412 KB Output is correct
10 Correct 185 ms 172096 KB Output is correct
11 Correct 176 ms 172084 KB Output is correct
12 Correct 166 ms 174544 KB Output is correct
13 Correct 162 ms 173888 KB Output is correct
14 Correct 173 ms 173336 KB Output is correct
15 Correct 165 ms 174788 KB Output is correct
16 Correct 162 ms 175952 KB Output is correct
17 Correct 164 ms 175956 KB Output is correct
18 Correct 176 ms 176724 KB Output is correct
19 Correct 181 ms 183204 KB Output is correct
20 Correct 169 ms 182968 KB Output is correct
21 Correct 174 ms 182684 KB Output is correct
22 Correct 42 ms 94412 KB Output is correct
23 Correct 46 ms 94504 KB Output is correct
24 Correct 41 ms 94504 KB Output is correct
25 Correct 42 ms 94492 KB Output is correct
26 Incorrect 42 ms 94484 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #2
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 94316 KB Output is correct
2 Correct 42 ms 94264 KB Output is correct
3 Correct 47 ms 94480 KB Output is correct
4 Correct 43 ms 94512 KB Output is correct
5 Correct 788 ms 140872 KB Output is correct
6 Correct 580 ms 140848 KB Output is correct
7 Correct 1035 ms 140848 KB Output is correct
8 Correct 634 ms 140832 KB Output is correct
9 Correct 749 ms 140932 KB Output is correct
10 Correct 351 ms 140980 KB Output is correct
11 Correct 342 ms 140972 KB Output is correct
12 Correct 343 ms 140916 KB Output is correct
13 Correct 339 ms 140912 KB Output is correct
14 Correct 350 ms 140864 KB Output is correct
15 Correct 641 ms 141032 KB Output is correct
16 Correct 878 ms 140996 KB Output is correct
17 Correct 738 ms 140956 KB Output is correct
18 Correct 385 ms 141180 KB Output is correct
19 Correct 343 ms 141168 KB Output is correct
20 Correct 346 ms 141036 KB Output is correct
21 Correct 345 ms 141152 KB Output is correct
22 Correct 339 ms 141640 KB Output is correct
23 Correct 344 ms 141644 KB Output is correct
24 Correct 344 ms 141584 KB Output is correct
25 Execution timed out 2068 ms 130824 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #3
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 94284 KB Output is correct
2 Correct 39 ms 94240 KB Output is correct
3 Correct 164 ms 171836 KB Output is correct
4 Correct 186 ms 171868 KB Output is correct
5 Correct 169 ms 171900 KB Output is correct
6 Correct 186 ms 171932 KB Output is correct
7 Correct 174 ms 172052 KB Output is correct
8 Correct 177 ms 172112 KB Output is correct
9 Correct 193 ms 172412 KB Output is correct
10 Correct 185 ms 172096 KB Output is correct
11 Correct 176 ms 172084 KB Output is correct
12 Correct 166 ms 174544 KB Output is correct
13 Correct 162 ms 173888 KB Output is correct
14 Correct 173 ms 173336 KB Output is correct
15 Correct 165 ms 174788 KB Output is correct
16 Correct 162 ms 175952 KB Output is correct
17 Correct 164 ms 175956 KB Output is correct
18 Correct 176 ms 176724 KB Output is correct
19 Correct 181 ms 183204 KB Output is correct
20 Correct 169 ms 182968 KB Output is correct
21 Correct 174 ms 182684 KB Output is correct
22 Correct 42 ms 94412 KB Output is correct
23 Correct 46 ms 94504 KB Output is correct
24 Correct 41 ms 94504 KB Output is correct
25 Correct 42 ms 94492 KB Output is correct
26 Incorrect 42 ms 94484 KB Output isn't correct
27 Halted 0 ms 0 KB -