Submission #1083457

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083457		vjudge1	Valley (BOI19_valley)	C++17	100 / 100	109 ms	43540 KiB

valley

#include <bits/stdc++.h>

#define endl '\n'

using namespace std;

void FastIO(string name = "")
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    if (name.empty() == 0)
    {
        freopen((name + ".in").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }
}

const int ct = 2e5;
const long long inf = 1e18;

vector<pair<int, int>> adj[ct];
int in[ct], out[ct];
long long dis[ct] , dis2[ct] ;
int table[ct][20];
long long best[ct][20];
bool shope[ct];

int timer;
void dfs(int at, int prv)
{
    in[at] = timer++;
    best[at][0] = inf;

    table[at][0] = prv;

    if (shope[at])
    {
        best[at][0] = 0;
    }

    for (auto &[to, w] : adj[at])
        if (to != prv)
        {
            dis[to] = dis[at] + 1;
            dis2[to] = dis2[at] + w ;            
            dfs(to, at);
            best[at][0] = min(best[at][0], best[to][0] + w);
        }
    
    out [at] = timer ++; 
};

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

void solve()
{
    int n, s, q, e;
    cin >> n >> s >> q >> e;

    vector<array<int, 3>> edge(n);
    for (int i = 1; i < n; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
        edge[i] = {u, v, w};
    }

    for (int i = 0; i < s; i++)
    {
        int x;
        cin >> x;
        shope[x] = 1;
    }
        
    dfs(e, 0);

    for(int i =1 ; i <= n ; i ++)
    {
        best[i][0] -= dis2[i] ;
    }
    
    for (int bit = 1; bit < 20; bit++)
        for (int i = 1; i <= n; i++)
        {
            table[i][bit] = table[table[i][bit - 1]][bit - 1];
            best[i][bit] = min(best[i][bit - 1], best[table[i][bit - 1]][bit - 1]);
        }

    while (q--)
    {
        int road, node;
        cin >> road >> node;

        int u = edge[road][0], v = edge[road][1];

        if (ancestor(v, u))
            swap(u, v);

        if (ancestor(v, node))
        {
            int need = dis[node] - dis[v] + 1;
            long long add = dis2[node] ;
            
            long long result = inf;
            for (int bit = 0; bit < 20; bit++)
                if (need >> bit & 1)
                {
                    result = min(result, best[node][bit]);
                    node = table[node][bit];
                }
                
            result += add ;
            if (result >= inf/2)
                cout << "oo" << endl;
            else
                cout << result << endl;
        }
        else
        {
            cout << "escaped" << endl;
        }
    }
}

int main()
{
    FastIO("");

    int t = 1;
    //cin >> t;

    for (int i = 0; i < t; i++)
    {
        solve();
    }
}

Compilation message (stderr)

valley.cpp: In function 'void FastIO(std::string)':
valley.cpp:14:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |         freopen((name + ".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:15:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |         freopen((name + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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