Submission #556992

#	Time	Username	Problem	Language	Result	Execution time	Memory
556992		Tien_Noob	Valley (BOI19_valley)	C++17	100 / 100	276 ms	50068 KiB

valley

//Make CSP great again
//Vengeance
#include <bits/stdc++.h>
#define TASK "TESTCODE"
#define Log2(x) 31 - __builtin_clz(x)
using namespace std;
const int N = 1e5;
const long long oo = 1e18;
long long dp[N + 1], f[N + 1];
int n, s, q, root, tin[N + 1], depth[N + 1], tout[N + 1], timer, l[N], r[N], w[N];
vector<int> adj[N + 1];
vector<pair<int, int> > query[N + 1];
bool shop[N + 1];
long long res[N + 1];
void read()
{
    cin >> n >> s >> q >> root;
    for (int i = 1; i < n; ++ i)
    {
        cin >> l[i] >> r[i] >> w[i];
        adj[l[i]].push_back(i);
        adj[r[i]].push_back(i);
    }
    for (int i = 1; i <= s; ++ i)
    {
        int u;
        cin >> u;
        shop[u] = true;
    }
    for (int i = 1; i <= q; ++ i)
    {
        int I, R;
        cin >> I >> R;
        query[R].push_back({I, i});
    }
    depth[root] = 1;
    fill(res, res + q + 1, oo);
}
struct FenwickTree
{
    multiset<long long> tree[N + 1];
    void add(int pos, long long val)
    {
        for (; pos > 0; pos -= (pos & (-pos)))
        {
            tree[pos].insert(val);
        }
    }
    long long get(int pos)
    {
        long long ret = oo;
        for (; pos <= n; pos += (pos & (-pos)))
        {
            if (!tree[pos].empty())
            {
                ret = min(ret, *tree[pos].begin());
            }
        }
        return ret;
    }
    void del(int pos, long long val)
    {
        for (; pos > 0; pos -= (pos & (-pos)))
        {
            auto it = tree[pos].find(val);
            if (it != tree[pos].end())
            {
                tree[pos].erase(it);
            }
        }
    }
} tree;
void preDFS(int u, int p)
{
    tin[u] = ++timer;
    if (shop[u])
    {
        dp[u] = f[u];
    }
    else
    {
        dp[u] = oo;
    }
    for (int i : adj[u])
    {
        int v = l[i] ^ r[i] ^ u;
        if (v == p)
        {
            continue;
        }
        f[v] = f[u] + w[i];
        depth[v] = depth[u] + 1;
        preDFS(v, u);
        dp[u] = min(dp[u], dp[v]);
    }
    tout[u] = timer;
}
void DFS(int u, int p)
{
    if (dp[u] != oo)
    {
        tree.add(depth[u], dp[u] - 2 * f[u]);
    }
    for (auto &x : query[u])
    {
        if (depth[l[x.first]] > depth[r[x.first]])
        {
            swap(l[x.first], r[x.first]);
        }
        int b = r[x.first];
        if (tin[u] < tin[b] || tin[u] > tout[b])
        {
            res[x.second] = -1;
            continue;
        }
        long long t = tree.get(depth[b]);
        if (t != oo)
        {
            res[x.second] = t + f[u];
        }
    }
    for (int i : adj[u])
    {
        int v = l[i] ^ r[i] ^ u;
        if (v == p)
        {
            continue;
        }
        DFS(v, u);
    }
    if (dp[u] != oo)
    {
        tree.del(depth[u], dp[u] - 2 * f[u]);
    }
}
void solve()
{
    preDFS(root, 0);
    DFS(root, 0);
    for (int i = 1; i <= q; ++ i)
    {
        if (res[i] == -1)
        {
            cout << "escaped" << '\n';
        }
        else if (res[i] == oo)
        {
            cout << "oo" << '\n';
        }
        else
        {
            cout << res[i] << '\n';
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    if (fopen(TASK".INP", "r"))
    {
        freopen(TASK".INP", "r", stdin);
        //freopen(TASK".OUT", "w", stdout);
    }
    int t = 1;
    bool typetest = false;
    if (typetest)
    {
        cin >> t;
    }
    for (int __ = 1; __ <= t; ++ __)
    {
        //cout << "Case " << __ << ": ";
        read();
        solve();
    }
}

Compilation message (stderr)

valley.cpp: In function 'int main()':
valley.cpp:162:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  162 |         freopen(TASK".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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