제출 #1104955

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1104955		underwaterkillerwhale	Valley (BOI19_valley)	C++17	100 / 100	141 ms	38996 KiB

valley

#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define MAXN 100005
#define ii pair<int,int>
#define bit(i,j) ((i>>j)&1)
#define sz(i) (int)i.size()
#define endl '\n'
using namespace std;
const ll INF = 1e18 + 7;
int n, m, ntest, root;
int a[MAXN];
ii edge[MAXN];
vector<ii>g[MAXN];
namespace sub1
{
int timedfs;
int h[MAXN],f[MAXN][20];
ll dp[MAXN], s[MAXN],val[MAXN][20];
ii range[MAXN];
int log2(int x)
{
  if (x == 0) return 0;
    return 32 - __builtin_clz(x) - 1;
}
void init(int u, int p)
{
    if(a[u])
        dp[u] = s[u];
    for(ii i : g[u])
    {
        int v = i.F, w = i.S;
        if(v == p)
            continue;
        s[v] = s[u] + w;
        init(v, u);
        dp[u]=min(dp[u],dp[v]);
    }
}
void dfs(int u, int p)
{
    range[u].F = ++timedfs;
    h[u] = h[p] + 1;
    f[u][0] = p;
    val[u][0] = dp[p] - 2 * s[p];
    for(int i = 1; i <= 18; i++)
    {
        f[u][i] = f[f[u][i - 1]][i - 1];
        val[u][i] = min(val[u][i - 1], val[f[u][i - 1]][i - 1]);
    }
    for(ii i : g[u])
    {
        int v = i.F;
        if(v == p)
            continue;
        dfs(v, u);
    }
    range[u].S = timedfs;
}
void ans(int u, int v)
{
    if(h[u]<h[v])
        swap(u,v);
    int delta = h[u] - h[v], curu = u;
    ll res = dp[u]-2*s[u];
    for(int i = log2(delta); i >= 0; i--)
        if(bit(delta, i))
        {
            res = min(res, val[u][i]);
            u = f[u][i];
        }
    if(res + s[curu] > 1e14)
        return cout << "oo\n", void();
    cout << res + s[curu] << endl;
}
bool check(int u, int v, int x)
{
    if(range[x].F >= range[u].F && range[x].F <= range[u].S && range[x].F >= range[v].F && range[x].F <= range[v].S)
        return 0;
    return 1;
}
void solve()
{
    for(int i = 1; i <= n; i++)
    {
        dp[i] = INF;
        for(int j = 0; j <= 18; j++)
            val[i][j] = INF;
    }
    init(root, 0);
    dfs(root, 0);
    while(ntest--)
    {
        int id, u;
        cin >> id >> u;
        if(check(edge[id].F, edge[id].S, u))
            cout << "escaped\n";
        else if(h[edge[id].F] > h[edge[id].S])
            ans(u, edge[id].F);
        else
            ans(u, edge[id].S);
    }
}
}
main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> ntest >> root;
    for(int i = 1; i < n; i++)
    {
        int x, y, z;
        cin >> x >> y >> z;
        edge[i] = {x, y};
        g[x].push_back({y, z});
        g[y].push_back({x, z});
    }
    for(int i = 1; i <= m; i++)
    {
        int x;
        cin >> x;
        a[x] = 1;
    }
    sub1::solve();
}
/**
10 2 1 9
7 1 3
9 2 3
10 5 1
8 7 3
10 1 3
5 6 2
2 1 2
3 1 1
4 2 2
2
7
7 3
**/

컴파일 시 표준 에러 (stderr) 메시지

valley.cpp:106:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  106 | main()
      | ^~~~

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