제출 #1104908

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1104908		whoknow	Valley (BOI19_valley)	C++17	100 / 100	122 ms	36612 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][18];
ll dp[MAXN], s[MAXN],val[MAXN][18];
ii range[MAXN];
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 <= 16; 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)
{
    int delta = h[u] - h[v], curu = u;
    ll res = dp[u]-2*s[u];
    for(int i = 0; i <= log2(delta); 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 <= 16; 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()
{
    if(fopen("TEST.inp","r"))
    {
        freopen("TEST.inp","r",stdin);
        freopen("TEST.out","w",stdout);
    }
    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:99:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   99 | main()
      | ^~~~
valley.cpp: In function 'int main()':
valley.cpp:103:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |         freopen("TEST.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
valley.cpp:104:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |         freopen("TEST.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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