Submission #802584

# Submission time Handle Problem Language Result Execution time Memory
802584 2023-08-02T12:49:40 Z ashcomp LOSTIKS (INOI20_lostiks) C++14
0 / 100
263 ms 196176 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<<2] , rmq[maxn<<2][25] , ps_rmq[maxn<<2][25] , rrmq[maxn<<2][25] , ps_rrmq[maxn<<2][25] , len[maxn<<2];
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[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<25; 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(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 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){
                                int tp = dfs(u,tm,end);
                                if(tp==-1)return -1;
                        }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;
                                        tp = dfs(u,tm,end);
                                        if(tp==-1)return -1;
                                }else{
                                        int tp = dfs(u,tm,end);
                                        if(tp==-1)return -1;
                                }
                        }
                }
        }
        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 46 ms 94324 KB Output is correct
2 Correct 49 ms 94256 KB Output is correct
3 Correct 263 ms 193196 KB Output is correct
4 Correct 255 ms 193368 KB Output is correct
5 Correct 241 ms 193244 KB Output is correct
6 Correct 253 ms 193336 KB Output is correct
7 Correct 236 ms 193440 KB Output is correct
8 Correct 227 ms 193548 KB Output is correct
9 Correct 230 ms 193836 KB Output is correct
10 Correct 234 ms 193568 KB Output is correct
11 Correct 242 ms 193580 KB Output is correct
12 Correct 215 ms 194104 KB Output is correct
13 Incorrect 225 ms 196176 KB Output isn't correct
14 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 44 ms 94292 KB Output is correct
2 Correct 45 ms 94308 KB Output is correct
3 Incorrect 46 ms 94464 KB Output isn't correct
4 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 46 ms 94324 KB Output is correct
2 Correct 49 ms 94256 KB Output is correct
3 Correct 263 ms 193196 KB Output is correct
4 Correct 255 ms 193368 KB Output is correct
5 Correct 241 ms 193244 KB Output is correct
6 Correct 253 ms 193336 KB Output is correct
7 Correct 236 ms 193440 KB Output is correct
8 Correct 227 ms 193548 KB Output is correct
9 Correct 230 ms 193836 KB Output is correct
10 Correct 234 ms 193568 KB Output is correct
11 Correct 242 ms 193580 KB Output is correct
12 Correct 215 ms 194104 KB Output is correct
13 Incorrect 225 ms 196176 KB Output isn't correct
14 Halted 0 ms 0 KB -