Submission #556888

#	Time	Username	Problem	Language	Result	Execution time	Memory
556888		Tien_Noob	Valley (BOI19_valley)	C++17	0 / 100	598 ms	56804 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 , cbit = 16;
int f[N + 1][cbit + 1], depth[N + 1], l[N + 1], r[N + 1], w[N + 1], sz[N + 1], par[N + 1], timer, n, s, q, e;
long long g[N + 1];
bool visited[N + 1];
set<pair<long long, int> > dp[N + 1];
vector<int> adj[N + 1];
void read()
{
    cin >> n >> s >> q >> e;
    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);
    }
}
void DFS(int u, int p)
{
    for (int x: adj[u])
    {
        int v = l[x] ^ r[x] ^ u;
        if (v == p)
        {
            continue;
        }
        depth[v] = depth[u] + 1;
        g[v] = g[u] + w[x];
        f[v][0] = u;
        for (int i = 1; i <= cbit; ++ i)
        {
            f[v][i] = f[f[v][i - 1]][i - 1];
        }
        DFS(v, u);
    }
}
int LCA(int u, int v)
{
    if (depth[v] < depth[u])
    {
        swap(u, v);
    }
    int k = depth[v] - depth[u];
    for (int i = cbit; i >= 0; -- i)
    {
        if ((k >> i) & 1)
        {
            v = f[v][i];
        }
    }
    if (u == v)
    {
        return u;
    }
    for (int i = cbit; i >= 0; -- i)
    {
        if (f[u][i] != f[v][i])
        {
            u = f[u][i];
            v = f[v][i];
        }
    }
    return f[u][0];
}
long long dis(int u, int v)
{
    int k = LCA(u, v);
    return g[u] + g[v] - 2 * g[k];
}
void CenDFS(int u, int p)
{
    sz[u] = 1;
    for (int x : adj[u])
    {
        int v = l[x] ^ r[x] ^ u;
        if (v == p || visited[v])
        {
            continue;
        }
        CenDFS(v, u);
        sz[u] += sz[v];
    }
}
int FindCentroid(int u, int p, int s)
{
    for (int x : adj[u])
    {
        int v = l[x] ^ r[x] ^ u;
        if (v == p || visited[v])
        {
            continue;
        }
        if (sz[v] > s/2)
        {
            return FindCentroid(v, u, s);
        }
    }
    return u;
}
int BuildCentroid(int u)
{
    CenDFS(u, 0);
    int root = FindCentroid(u, 0, sz[u]);
    visited[root] = true;
    for (int x : adj[root])
    {
        int v = l[x] ^ r[x] ^ root;
        if (visited[v])
        {
            continue;
        }
        par[BuildCentroid(v)] = root;
    }
    return root;
}
void update(int u)
{
    for (int v = u; v > 0; v = par[v])
    {
        dp[v].insert({dis(u, v), u});
    }
}
int nchain = 1, chain[N + 1], pos[N + 1], head[N + 1];
void preHLD(int u, int p)
{
    sz[u] = 1;
    for (int x : adj[u])
    {
        int v = l[x] ^ r[x] ^ u;
        if (v == p)
        {
            continue;
        }
        preHLD(v, u);
        sz[u] += sz[v];
    }
}
struct FenwickTree
{
    int tree[N + 1];
    void add(int pos, int val)
    {
        for (; pos <= n; pos += (pos & (-pos)))
        {
            tree[pos] += val;
        }
    }
    int sum(int pos)
    {
        int ret = 0;
        for (; pos > 0; pos -= (pos & (-pos)))
        {
            ret += tree[pos];
        }
        return ret;
    }
    int sum(int l, int r)
    {
        if (l > r)
        {
            return 0;
        }
        return sum(r) - sum(l - 1);
    }
} tree;
void HLD(int u, int p)
{
    int bigchild = -1;
    chain[u] = nchain;
    pos[u] = ++timer;
    if (head[nchain] == 0)
    {
        head[nchain] = u;
    }
    for (int x : adj[u])
    {
        int v = l[x] ^ r[x] ^ u;
        if (v == p)
        {
            continue;
        }
        if (bigchild == -1 || sz[bigchild] < sz[v])
        {
            bigchild = v;
        }
    }
    if (bigchild != -1)
    {
        HLD(bigchild, u);
    }
    for (int x : adj[u])
    {
        int v = l[x] ^ r[x] ^ u;
        if (v == bigchild || v == p)
        {
            continue;
        }
        ++nchain;
        HLD(v, u);
    }
}
bool reachable(int u, int p)
{
    while(chain[u] != chain[p])
    {
        if (tree.sum(pos[head[chain[u]]], pos[u]) > 0)
        {
            return false;
        }
        u = f[head[chain[u]]][0];
    }
    return tree.sum(pos[p] + 1, pos[u]) == 0;
}
bool reach(int u, int v)
{
    int k = LCA(u, v);
    return reachable(u, k) && reachable(v, k);
}
int get(int u)
{
    long long res = -1;
    for (int v = u; v > 0; v = par[v])
    {
        while(!dp[v].empty() && !reach(dp[v].begin()->second, v))
        {
            dp[v].erase(dp[v].begin());
        }
        if (reach(u, v) && !dp[v].empty())
        {
            if (res == -1 || res > dp[v].begin()->first + dis(u, v))
            {
                res = dp[v].begin()->first + dis(u, v);
            }
        }
    }
    return res;
}
void prepare()
{
    DFS(1, 0);
    par[BuildCentroid(1)] = 0;
    timer = 0;
    preHLD(1, 0);
    HLD(1, 0);
    for (int i = 1; i <= s; ++ i)
    {
        int u;
        cin >> u;
        update(u);
    }
    fill(visited + 1, visited + n, false);
    /*for (int i = 1; i <= n; ++ i)
    {
        cerr << chain[i] << '\n';
    }*/
}
void solve()
{
    prepare();
    while(q--)
    {
        int i, u;
        cin >> i >> u;
        if (!visited[i])
        {
            visited[i] = true;
            if (depth[l[i]] > depth[r[i]])
            {
                swap(l[i], r[i]);
            }
            tree.add(pos[r[i]], 1);
        }
        if (reach(u, e))
        {
            cout << "escaped" << '\n';
            continue;
        }
        long long res = get(u);
        if (res == -1)
        {
            cout << "oo" << '\n';
        }
        else
        {
            cout << res << '\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:300:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  300 |         freopen(TASK".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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