oj.uz

Submission #806761

# Submission time Handle Problem Language Result Execution time Memory
806761 2023-08-04T09:38:23 Z ashcomp LOSTIKS (INOI20_lostiks) C++14
23 / 100
 2000 ms 369036 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")
#pragma GCC optimize("-O2")
 
const ll INF = 1e9;
const ll maxn = 2e6 + 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][22] , ps_rmq[maxn<<1][22] , rrmq[maxn<<1][22] , ps_rrmq[maxn<<1][22] , 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;
        
}
inline 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
inline 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];
        }
}
inline 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);
        }
        if((int)EG.size()>20){
                cout<<"COSNANAT";
                return 0;
        }
        /**/
        pre_LCA();
        for(int i=1; i<=n; i++){
                p[i] = -1;
        }
        dfs(ST);
        for(int i=1; i<(1<<((int)EG.size()))+(1<<((int)EG.size())); i++){
                for(int j=0; j<((int)EG.size())+1; j++){
                        dp[i][j] = INF;
                }
        }
        for(int i=1; i<(1<<((int)EG.size())); i++){
                int pos = i;
                while(pos>0){
                        int j = __builtin_ctz(pos);
                        pos -= (1<<j);
                        int x = i^(1<<j);
                        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;
                        }
                        int POS=i;
                        while(POS>0){
                                int f = __builtin_ctz(POS);
                                POS -= 1<<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);
                                }
                                dp[i][j] = min(dp[i][j] , dp[x][f]+DIS(v,W)+min(DIS(W,V),DIS(W,U)) );
                        }
                }
        }
        /***********************************/
        ps = ((int)EG.size());
        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}});
 
        for(int i=(1<<ps); i<(1<<(ps+1)); i++){
                int j = ps;
                int x = i^(1<<j);
                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;
                }
                int POS=i;
                while(POS>0){
                        int f = __builtin_ctz(POS);
                        POS -= 1<<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);
                        }
                        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<<ps); i<(1<<(ps+1)); i++){
                ans = min(ans , dp[i][ps]);
        }
        /*ll 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 , (ll)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
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 188240 KB Output is correct
2 Correct 73 ms 188168 KB Output is correct
3 Correct 210 ms 269052 KB Output is correct
4 Correct 226 ms 269060 KB Output is correct
5 Correct 204 ms 269052 KB Output is correct
6 Correct 219 ms 268956 KB Output is correct
7 Correct 211 ms 269180 KB Output is correct
8 Correct 237 ms 269140 KB Output is correct
9 Correct 238 ms 269464 KB Output is correct
10 Correct 243 ms 269180 KB Output is correct
11 Correct 215 ms 269172 KB Output is correct
12 Correct 215 ms 271708 KB Output is correct
13 Correct 209 ms 270976 KB Output is correct
14 Correct 220 ms 270308 KB Output is correct
15 Correct 230 ms 271976 KB Output is correct
16 Correct 226 ms 273004 KB Output is correct
17 Correct 208 ms 273036 KB Output is correct
18 Correct 224 ms 273860 KB Output is correct
19 Correct 229 ms 280388 KB Output is correct
20 Correct 203 ms 280108 KB Output is correct
21 Correct 221 ms 279672 KB Output is correct
22 Correct 77 ms 188360 KB Output is correct
23 Correct 78 ms 188408 KB Output is correct
24 Correct 79 ms 188380 KB Output is correct
25 Correct 76 ms 188364 KB Output is correct
26 Correct 75 ms 188464 KB Output is correct

Subtask #2
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 188160 KB Output is correct
2 Correct 76 ms 188200 KB Output is correct
3 Correct 77 ms 188556 KB Output is correct
4 Correct 76 ms 188540 KB Output is correct
5 Correct 584 ms 284272 KB Output is correct
6 Correct 430 ms 284364 KB Output is correct
7 Correct 714 ms 284348 KB Output is correct
8 Correct 522 ms 284392 KB Output is correct
9 Correct 576 ms 284360 KB Output is correct
10 Correct 280 ms 284268 KB Output is correct
11 Correct 279 ms 284296 KB Output is correct
12 Correct 286 ms 284460 KB Output is correct
13 Correct 275 ms 284380 KB Output is correct
14 Correct 283 ms 284396 KB Output is correct
15 Correct 573 ms 284316 KB Output is correct
16 Correct 669 ms 284396 KB Output is correct
17 Correct 554 ms 284364 KB Output is correct
18 Correct 287 ms 284564 KB Output is correct
19 Correct 288 ms 284612 KB Output is correct
20 Correct 288 ms 284612 KB Output is correct
21 Correct 268 ms 284696 KB Output is correct
22 Correct 284 ms 285152 KB Output is correct
23 Correct 284 ms 285144 KB Output is correct
24 Correct 271 ms 285096 KB Output is correct
25 Execution timed out 2078 ms 369036 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #3
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 188240 KB Output is correct
2 Correct 73 ms 188168 KB Output is correct
3 Correct 210 ms 269052 KB Output is correct
4 Correct 226 ms 269060 KB Output is correct
5 Correct 204 ms 269052 KB Output is correct
6 Correct 219 ms 268956 KB Output is correct
7 Correct 211 ms 269180 KB Output is correct
8 Correct 237 ms 269140 KB Output is correct
9 Correct 238 ms 269464 KB Output is correct
10 Correct 243 ms 269180 KB Output is correct
11 Correct 215 ms 269172 KB Output is correct
12 Correct 215 ms 271708 KB Output is correct
13 Correct 209 ms 270976 KB Output is correct
14 Correct 220 ms 270308 KB Output is correct
15 Correct 230 ms 271976 KB Output is correct
16 Correct 226 ms 273004 KB Output is correct
17 Correct 208 ms 273036 KB Output is correct
18 Correct 224 ms 273860 KB Output is correct
19 Correct 229 ms 280388 KB Output is correct
20 Correct 203 ms 280108 KB Output is correct
21 Correct 221 ms 279672 KB Output is correct
22 Correct 77 ms 188360 KB Output is correct
23 Correct 78 ms 188408 KB Output is correct
24 Correct 79 ms 188380 KB Output is correct
25 Correct 76 ms 188364 KB Output is correct
26 Correct 75 ms 188464 KB Output is correct
27 Correct 75 ms 188160 KB Output is correct
28 Correct 76 ms 188200 KB Output is correct
29 Correct 77 ms 188556 KB Output is correct
30 Correct 76 ms 188540 KB Output is correct
31 Correct 584 ms 284272 KB Output is correct
32 Correct 430 ms 284364 KB Output is correct
33 Correct 714 ms 284348 KB Output is correct
34 Correct 522 ms 284392 KB Output is correct
35 Correct 576 ms 284360 KB Output is correct
36 Correct 280 ms 284268 KB Output is correct
37 Correct 279 ms 284296 KB Output is correct
38 Correct 286 ms 284460 KB Output is correct
39 Correct 275 ms 284380 KB Output is correct
40 Correct 283 ms 284396 KB Output is correct
41 Correct 573 ms 284316 KB Output is correct
42 Correct 669 ms 284396 KB Output is correct
43 Correct 554 ms 284364 KB Output is correct
44 Correct 287 ms 284564 KB Output is correct
45 Correct 288 ms 284612 KB Output is correct
46 Correct 288 ms 284612 KB Output is correct
47 Correct 268 ms 284696 KB Output is correct
48 Correct 284 ms 285152 KB Output is correct
49 Correct 284 ms 285144 KB Output is correct
50 Correct 271 ms 285096 KB Output is correct
51 Execution timed out 2078 ms 369036 KB Time limit exceeded
52 Halted 0 ms 0 KB -