Submission #1093952

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093952		Requiem	Valley (BOI19_valley)	C++17	100 / 100	199 ms	90644 KiB

valley

#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define inf 1000000000000000000
#define fi first
#define se second
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define sz(a) ((int)(a).size())
#define endl '\n'
#define pi 3.14159265359
#define TASKNAME "valley"
using namespace std;
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;


const int MAXN = 3e5 + 9;
iii edge[MAXN];
int n, s, q, e;

vector<int> shops;
vector<ii> queries;
int isShop[MAXN];
vector<int> g[MAXN];
array<int, 4> best[MAXN];
namespace subtask2{
    bool check(){
        return true;
    }

    int up[30][MAXN], down[30][MAXN], P[30][MAXN];
    int depth[MAXN], dp[MAXN], dist[MAXN], in[MAXN], out[MAXN], timeDfs = 0;

    void update(array<int, 4> &res, int x){
        FOR(i, 0, 3){
            if (x < res[i]){
                FORD(j, 3, i + 1){
                    res[j] = res[j - 1];
                }
                res[i] = x;
                break;
            }
        }
    }

    int choose(array<int, 4> &res, vector<int> eliminate){
        sort(eliminate.begin(), eliminate.end());
        assert(eliminate.size() < 4);
        FOR(i, 0, 3){
            if (i >= eliminate.size()) return res[i];
            if (res[i] != eliminate[i]) return res[i];
        }
        return 0;
    }

    inline int getDist(int u, int v){
        return abs(dist[v] - dist[u]);
    }

    void init(){
        function<void(int, int)> dfs = [&](int u, int p){
            best[u] = {inf, inf, inf, inf};
            in[u] = ++timeDfs;
            dp[u] = inf;
            if (isShop[u]) {
                minimize(dp[u], 0LL);
                update(best[u], 0LL);
            }
            for(int id: g[u]){
                int v = edge[id].se.fi + edge[id].se.se - u;
                int w = edge[id].fi;
                if (v == p) continue;
                depth[v] = depth[u] + 1;
                dist[v] = dist[u] + w;
                dfs(v, u);
                minimize(dp[u], dp[v] + w);
                update(best[u], dp[v] + w);
                P[0][v] = u;
            }
            for(int id: g[u]){
                int v = edge[id].se.fi + edge[id].se.se - u;
                int w = edge[id].fi;
                if (v == p) continue;
                up[0][v] = (isShop[v]) ? 0 : choose(best[u], {dp[v] + w}) + w;
                down[0][v] = min((isShop[v]) ? (w) : inf, choose(best[u], {dp[v] + w}));
            }
            out[u] = timeDfs;
        };
        dfs(1, -1);
        P[0][1] = -1; up[0][1] = (isShop[1]) ? 0 : inf;  down[0][1] = inf;
//        printf("\n");
//        FOR(i, 1, n){
//            printf("%lld ", down[0][i]);
//        }
//        printf("\n");
        FOR(i, 1, 20){
            FOR(j, 1, n){
                if (P[i - 1][j] == -1) P[i][j] = -1;
                else P[i][j] = P[i - 1][P[i - 1][j]];

                up[i][j] = down[i][j] = inf;
                if (P[i][j] != -1){
                    up[i][j] = min(up[i - 1][P[i - 1][j]] + getDist(P[i - 1][j], j),
                                   up[i - 1][j]);
                    down[i][j] = min(down[i - 1][P[i - 1][j]],
                                     down[i - 1][j] + getDist(P[i - 1][j], P[i][j]));
                }
//                printf("%lld ", down[i][j]);
            }
//            printf("\n\n");
        }
    }

    int getPath(int u, int v, bool Up){ //tu u den v va chieu cao can thiet d, Up: 1 trong 2 case.
        int cur, res;
        if (Up){  //di tu u len v
            res = inf;
            cur = u;
            FORD(i, 20, 0){
                 if (P[i][cur] != -1 and depth[P[i][cur]] >= depth[v]){
                     minimize(res, getDist(u, cur) + up[i][cur]);
                     cur = P[i][cur];
                 }
            }
        }

        else{  //di xuong tu u xuong v
            cur = v;
            res = inf;
            FORD(i, 20, 0){
                if (P[i][cur] != -1 and depth[P[i][cur]] >= depth[u]){
                    minimize(res, getDist(u, P[i][cur]) + down[i][cur]);
                    cur = P[i][cur];
                }
            }
        }
        return res;
    }

    int kthJump(int u, int k){
//        cerr << u << ' ' << k << endl;
        if (k < 0 or k > depth[u]) return -1;
        FORD(i, 20, 0){
            if (k & (1 << i)) u = P[i][u];
        }
        return u;
    }
    int getLCA(int u, int v){
        if (depth[u] < depth[v]) swap(u, v);
        FORD(i, 20, 0){
            if (P[i][u] != -1 and depth[P[i][u]] >= depth[v])  u = P[i][u];
        }
        if (u == v) return u;
        FORD(i, 20, 0){
            if (P[i][u] != -1 and P[i][v] != -1 and P[i][u] != P[i][v]) u = P[i][u], v = P[i][v];
        }
        return P[0][u];
    }

    inline bool inSubtree(int u, int v){ //u co nam trong cay con goc v hay khong
        return in[u] >= in[v] and in[u] <= out[v];
    }

    void solveQueries(){
        FOR(i, 1, q){
            int I, R;
            I = queries[i - 1].fi;
            R = queries[i - 1].se;
            int u = edge[I].se.fi;
            int v = edge[I].se.se;
            int w = edge[I].fi;
            if (depth[u] > depth[v]) swap(u, v);
            int res = inf;

            if ((inSubtree(R, v) ^ inSubtree(e, v)) == 0) {
                cout << "escaped\n";
            }
            else{
                if (isShop[R]) res = 0;

                if (inSubtree(R, v)){
                    minimize(res, getPath(R, v, 1));
                    minimize(res, choose(best[R], {}));
                }

                else if (inSubtree(R, u)){
                    int beforeR = kthJump(R, depth[R] - depth[u] - 1);
                    if (beforeR != -1) minimize(res, getPath(R, beforeR, 1));

                    if (R != u) minimize(res, choose(best[R], {}));

                    if (R == u) minimize(res, choose(best[u], {dp[v] + w}));
                    else minimize(res, choose(best[u], {dp[v] + w, dp[beforeR] + getDist(beforeR, u)})  + getDist(R, u));

                    minimize(res, getPath(u, 1, 1) + getDist(R, u));

                }

                else {
                    int acs = getLCA(u, R);
                    int beforeR = kthJump(R, depth[R] - depth[acs] - 1);
                    int beforeU = kthJump(u, depth[u] - depth[acs] - 1);
//                    printf("%lld %lld\n", R, acs);
                    if (R == acs){
                        minimize(res, choose(best[R], {dp[beforeU] + dist[beforeU] - dist[R]}));
                        minimize(res, getPath(R, u, 0));
                        minimize(res, choose(best[u], {dp[v] + w}) + getDist(R, u));
                        minimize(res, getPath(R, 1, 1));
                    }

                    else{

                        minimize(res, getPath(R, beforeR, 1));

                        minimize(res, choose(best[R], {}));
                        minimize(res, getDist(R, acs) + choose(best[acs],{dp[beforeU] + getDist(beforeU, acs), dp[beforeR] + getDist(beforeR, acs)}));
                        minimize(res, getPath(acs, u, 0) + getDist(acs, R));
//                        printf("%lld %lld %lld %lld\n",res, acs, u, getPath(acs, u, 0));
                        minimize(res, choose(best[u], {dp[v] + w}) + getDist(acs, R) + getDist(acs, u));
                        minimize(res, getPath(acs, 1, 1) + getDist(R, acs));
                    }
                }


                if (res < inf) cout << res << endl;
                else cout << "oo\n";
            }
        }
    }

    void solve(){
        init();
        solveQueries();

    }
}

main()
{
    fast;
    if (fopen(TASKNAME".inp","r")){
        freopen(TASKNAME".inp","r",stdin);
        freopen(TASKNAME".out","w",stdout);
    }
    cin >> n >> s >> q >> e;
    FOR(i, 1, n - 1){
        cin >> edge[i].se.fi >> edge[i].se.se >> edge[i].fi;
        g[edge[i].se.fi].pb(i);
        g[edge[i].se.se].pb(i);
    }

    FOR(i, 1, s){
        int u;
        cin >> u;
        shops.pb(u);
        isShop[u] = 1;
    }

    FOR(i, 1, q){
        int I, R;
        cin >> I >> R;
        queries.pb({I, R});
    }

    if (subtask2::check()) return subtask2::solve(), 0;

}
/**
Warning:
- MLE / TLE?
- Gioi han mang?
- Gia tri max phai luon gan cho -INF
- long long co can thiet khong?
- tran mang.
- code can than hon
- Nho sinh test de tranh RTE / TLE

--> Coi lai truoc khi nop
**/

Compilation message (stderr)

valley.cpp: In function 'long long int subtask2::choose(std::array<long long int, 4>&, std::vector<long long int>)':
valley.cpp:56:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |             if (i >= eliminate.size()) return res[i];
      |                 ~~^~~~~~~~~~~~~~~~~~~
valley.cpp: At global scope:
valley.cpp:244:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  244 | main()
      | ^~~~
valley.cpp: In function 'int main()':
valley.cpp:248:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  248 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:249:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  249 |         freopen(TASKNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 27 / 27
• Subtask 3: 23 / 23
• Subtask 4: 41 / 41