Submission #1281907

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281907		vuquangsang	Valley (BOI19_valley)	C++20	100 / 100	100 ms	40232 KiB

valley

#include <bits/stdc++.h>
using namespace std;

#define     el "\n"
#define     FOR(i,a,b) for(int i = (a), _b = (b); i <= _b; i++)
#define     FORD(i,a,b) for(int i = (a), _b = (b); i >= _b; i--)
#define     pb push_back
#define     fi first
#define     se second
#define     all(x) x.begin(),x.end()
#define     lg(x) __lg(x)
#define     alla(a,n) a+1,a+n+1
#define     ll long long


template <class T> bool maxi(T &x, T y) { if(x < y) { x = y ; return true ;} return false;}
template <class T> bool mini(T &x, T y) { if(x > y) { x = y ; return true ;} return false;}

const int N = 1e5 + 2;
const ll inf = 1e16 + 2;

struct Edge
{
    int x, y, w;
} E[N];
int n, k, q, tar, shop[N];
vector<pair<int, int>> adj[N];

void inp()
{
    cin >> n >> k >> q >> tar;

    FOR(i, 1, n - 1) {
        int x, y, w; cin >> x >> y >> w;
        adj[x].pb({y, w});
        adj[y].pb({x, w});
        E[i] = {x, y, w};
    }
    FOR(i, 1, k) cin >> shop[i];
}

/* Try your best
    No regrets */

namespace subtask_1
{

    int h[N], up[N][21];

    ll Val[N];

    void dfs(int u, int p)
    {
        up[u][0] = p;
        FOR(j, 1, lg(n)) up[u][j] = up[up[u][j - 1]][j - 1];

        for(pair<int, int> x : adj[u]) {
            int v = x.first, w = x.second;
            if(v == p) continue;
            h[v] = h[u] + 1;
            Val[v] = Val[u] + w;
            dfs(v, u);
        }
    }
    int LCA(int u, int v)
    {
        if(h[u] < h[v]) swap(u, v);
        FORD(j, lg(n), 0) if(h[up[u][j]] >= h[v]) {
            u = up[u][j];
        }
        if(u == v) return u;
        FORD(j, lg(n), 0) if(up[u][j] != up[v][j]) {
            u = up[u][j];
            v = up[v][j];
        }
        return up[u][0];
    }

    ll dist(int x, int y)
    {
        return Val[x] + Val[y] - 2 * Val[LCA(x, y)];
    }

    bool isMinDist(int x, int y, int id)
    {
        int u = E[id].x, v = E[id].y, w = E[id].w;

        if(dist(x, y) == dist(x, u) + dist(y, v) + w || dist(x, y) == dist(x, v) + dist(y, u) + w) return 1;
        return 0;
    }
    void slv()
    {
        dfs(1, 1);

        while(q--) {
            int id, u; cin >> id >> u;
            if(!isMinDist(u, tar, id)) {
                cout << "escaped" << el;
            }
            else {
                bool oki = 0;
                ll ans = inf;
                FOR(i, 1, k) {
                    if(!isMinDist(u, shop[i], id)) {
                        oki = 1;
                        mini(ans, dist(u, shop[i]));
                    }
                }
                if(oki) cout << ans << el;
                else cout << "oo" << el;
            }
        }
    }
}

namespace subtask_2
{

    ll near[N], dist[N];
    int h[N], up[N][21];
    ll val[N][21];

    int in[N], out[N], time = 0;

    void dfs(int u, int p)
    {
        in[u] = ++time;

        up[u][0] = p;
        FOR(j, 1, lg(n)) up[u][j] = up[up[u][j - 1]][j - 1];

        for(pair<int, int> x : adj[u]) {
            int v = x.first, w = x.second;
            if(v == p) continue;
            h[v] = h[u] + 1;
            dist[v] = dist[u] + w;
            dfs(v, u);
            mini(near[u], near[v] + w);
        }
        val[u][0] = near[u] - dist[u];

        out[u] = time;
    }

    bool isPar(int x, int y)
    {
        return in[x] <= in[y] && out[y] <= out[x];
    }

    ll getAns(int x, int u)
    {
        int dis = h[u] - h[x] + 1;

        int star = u;

        ll ans = inf;
        FORD(j, lg(n), 0) if(dis >> j & 1) {
            mini(ans, val[u][j]);

            u = up[u][j];
        }
        return (ans += dist[star]);
    }
    void slv()
    {
        for(int i = 1; i <= n; i++) near[i] = inf;
        for(int i = 1; i <= k; i++) {
            near[shop[i]] = 0;
        }
        dfs(tar, tar);

        for(int j = 1; j <= lg(n); j++) {
            for(int i = 1; i <= n; i++) {
                val[i][j] = min(val[i][j - 1], val[up[i][j - 1]][j - 1]);
            }
        }

//        for(int i = 1; i <= n; i++) cout << near[i] << " "; cout << el;

        while(q--) {
            int id, u; cin >> id >> u;
            int x = E[id].x, y = E[id].y;
            if(h[x] < h[y]) swap(x, y);

            if(!isPar(x, u)) {
                cout << "escaped" << el;
            }
            else {
                ll ans = getAns(x, u);
                if(ans >= inf) cout << "oo" << el;
                else cout << ans << el;
            }
        }
    }
}
/* Code slowly, think carefully */

main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    #define __Azul__ "valley"
    if(fopen(__Azul__".inp", "r")) {
        freopen(__Azul__".inp", "r", stdin);
        freopen(__Azul__".out", "w", stdout);
    }

    bool qs = 0;

    int T = 1;
    if(qs) cin >> T;
    while(T--) {
        inp();
        subtask_2::slv();
    }

    cerr << "\nTime" << 0.001 * clock() << "s "; return 0;


}

Compilation message (stderr)

valley.cpp:198:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  198 | main()
      | ^~~~
valley.cpp: In function 'int main()':
valley.cpp:204:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  204 |         freopen(__Azul__".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:205:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  205 |         freopen(__Azul__".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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