Submission #161712

#	Time	Username	Problem	Language	Result	Execution time	Memory
161712		karma	Valley (BOI19_valley)	C++14	100 / 100	348 ms	53116 KiB

valley

#include <bits/stdc++.h>
#define pb          emplace_back
#define ll          long long
#define fi          first
#define se          second
#define mp          make_pair

using namespace std;

const int N = int(1e5) + 7;
const int logN = 17;
const ll inf = (ll)1e18;
typedef pair<int, int> pii;

ll f[N], res, w, g[N][logN + 1], dis[N][logN + 1];
pii e[N];
bool shop[N];
int n, s, u, v, del, r, q, root, T = 0;
int p[N][logN + 1], in[N], h[N], out[N];
vector<pii> a[N];

void DFS(int u) {
    in[u] = ++T;
    if(shop[u]) f[u] = 0;
    else f[u] = inf;
    for(int j = 1; j <= logN; ++j) {
        p[u][j] = p[p[u][j - 1]][j - 1];
        dis[u][j] = dis[u][j - 1] + dis[p[u][j - 1]][j - 1];
    }
    for(pii& lst: a[u]) {
        int v = lst.fi; ll w = lst.se;
        if(v == p[u][0]) continue;
        p[v][0] = u, dis[v][0] = w;
        h[v] = h[u] + 1;
        DFS(v);
        f[u] = min(f[u], f[v] + w);
    }
    out[u] = ++T;
}

bool uIsParentOfv(int u, int v) {
    return in[u] <= in[v] && out[v] <= out[u];
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    #define Task        "test"
    if(fopen(Task".inp", "r")) {
        freopen(Task".inp", "r", stdin);
        freopen(Task".out", "w", stdout);
    }
    cin >> n >> s >> q >> root;
    for(int i = 1; i < n; ++i) {
        cin >> u >> v >> w;
        e[i] = mp(u, v);
        a[u].pb(v, w), a[v].pb(u, w);
    }
    for(int i = 1; i <= s; ++i) cin >> u, shop[u] = 1;
    DFS(root);
    for(int i = 1; i <= n; ++i) g[i][0] = min(inf, f[p[i][0]] + dis[i][0]);
    for(int j = 1; j <= logN; ++j) {
        for(int i = 1; i <= n; ++i) {
           g[i][j] = min(g[i][j - 1], g[p[i][j - 1]][j - 1] + dis[i][j - 1]);
        }
    }
    while(q --) {
        cin >> del >> r; /// cat canh del va dang o dinh r
        u = e[del].fi, v = e[del].se;
        if(uIsParentOfv(v, u)) swap(u, v); /// u is parent of v
        if(uIsParentOfv(v, r)) {
           res = f[r]; ll d = 0, dep = (h[r] - h[v]);
           for(int i = 0; i <= logN; ++i) {
              if(dep >> i & 1) {
                res = min(res, d + g[r][i]);
                d += dis[r][i];
                r = p[r][i];
              }
           }
           if(res >= inf) cout << "oo\n";
           else cout << res << '\n';
        } else cout << "escaped\n";
    }
}

Compilation message (stderr)

valley.cpp: In function 'int main()':
valley.cpp:50:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(Task".inp", "r", stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:51:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(Task".out", "w", stdout);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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