Submission #802535

# Submission time Handle Problem Language Result Execution time Memory
802535 2023-08-02T12:42:02 Z ashcomp LOSTIKS (INOI20_lostiks) C++14
0 / 100
288 ms 198248 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 = 1e18;
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);
        }
        if(g[v].size()==1 && v!=1){
                LSA.push_back(v);
        }
        en[v] = LSA.size()-1;
}
void pre_LCA()
{
        LSA.push_back(0);
        p[1] = -1;
        DFS(1);
        m = LSA.size()-1;
        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;
        }
}
int LCA(int v , int u)
{
        int l = min(st[v],st[u]) , r=max(en[v],en[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 times=0;
map<int,bool> mp[maxn];
vector<int> ORDER;
vector<pii> eg[maxn];
int dfs(int v , int tm , int end)
{
        //cout<<v<<"-->"<<end<<" : "<<tm<<"\n";
        if(times>20){
                return -1;
        }
        if(v==end){
                return 1;
        }
        for(auto e : eg[v]){
                int u=e.F , w=e.S;
                int now = h[end]+h[v]-h[LCA(end,v)]-h[LCA(end,v)];
                int then = h[end]+h[u]-h[LCA(end,u)]-h[LCA(end,u)];
                if(then < now){
                        if(w==0){
                                dfs(u,tm,end);
                        }else{
                                if(mp[v][u]==0){
                                        times++;
                                        int tp = dfs(v,times,w);
                                        if(tp==-1){
                                                return -1;
                                        }
                                        ORDER.push_back(w);
                                        ORDER.push_back(v);
                                        mp[v][u] = 1;
                                        mp[u][v] = 1;
                                        dfs(u,tm,end);
                                }else{
                                        dfs(u,tm,end);
                                }
                        }
                }
        }
        return 1;
}
 
int main()
{
        ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
        cin>>n>>ST>>EN;
        for(int i=1; i<n; i++){
                int v,u,w; cin>>v>>u>>w;
                if(w==0){
                        mp[v][u] = 1;
                        mp[u][v] = 1;
                }
                eg[v].push_back({u,w});
                eg[u].push_back({v,w});
                g[v].push_back(u);
                g[u].push_back(v);
        }
        pre_LCA();
        ORDER.push_back(ST);
        int tp = dfs(ST,1,EN);
        ORDER.push_back(EN);
        if(tp==-1){
                while(n>0){
                        cout<<"-1"<<endl;
                }
        }else{
                ll ans = 0 , sz=ORDER.size();
                for(int i=1; i<sz; i++){
                        int v = ORDER[i-1] , u=ORDER[i];
                        ans += h[v]+h[u]-h[LCA(v,u)]-h[LCA(v,u)]; 
                }
                cout<<ans;
        }
        return 0;
}
/*
6
1 6
1 2 0
1 3 0
3 4 0
4 5 2
5 6 1
ans = 10;
*/
/**
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;
*/
# Verdict Execution time Memory Grader output
1 Correct 39 ms 94296 KB Output is correct
2 Correct 37 ms 94288 KB Output is correct
3 Correct 269 ms 197524 KB Output is correct
4 Correct 250 ms 197684 KB Output is correct
5 Correct 282 ms 197728 KB Output is correct
6 Correct 274 ms 197796 KB Output is correct
7 Correct 240 ms 197840 KB Output is correct
8 Correct 288 ms 198016 KB Output is correct
9 Correct 260 ms 198248 KB Output is correct
10 Correct 250 ms 198060 KB Output is correct
11 Correct 264 ms 197956 KB Output is correct
12 Correct 212 ms 181688 KB Output is correct
13 Incorrect 213 ms 185028 KB Output isn't correct
14 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 38 ms 94284 KB Output is correct
2 Correct 44 ms 94200 KB Output is correct
3 Incorrect 39 ms 94420 KB Output isn't correct
4 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 39 ms 94296 KB Output is correct
2 Correct 37 ms 94288 KB Output is correct
3 Correct 269 ms 197524 KB Output is correct
4 Correct 250 ms 197684 KB Output is correct
5 Correct 282 ms 197728 KB Output is correct
6 Correct 274 ms 197796 KB Output is correct
7 Correct 240 ms 197840 KB Output is correct
8 Correct 288 ms 198016 KB Output is correct
9 Correct 260 ms 198248 KB Output is correct
10 Correct 250 ms 198060 KB Output is correct
11 Correct 264 ms 197956 KB Output is correct
12 Correct 212 ms 181688 KB Output is correct
13 Incorrect 213 ms 185028 KB Output isn't correct
14 Halted 0 ms 0 KB -