Submission #1281700

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281700		vuquangsang	Valley (BOI19_valley)	C++20	36 / 100	3093 ms	17580 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 = 1e18 + 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;
            }
        }
    }
}

/* 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_1::slv();
    }

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


}

Compilation message (stderr)

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

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