제출 #1100459

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1100459		tinnhiemnn	Valley (BOI19_valley)	C++17	23 / 100	103 ms	27328 KiB

valley

#include <bits/stdc++.h>
using namespace std;
#define file "file"
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pb push_back
#define mp make_pair
const int N=1e5+5;
int n,s,q,H,up[N][22],d[N],ss[N];
long long h[N];
vector<pii> E[N], edge;
bool a[N];

void dfs(int u)
{
    for (pii p : E[u])
    {
        int v=p.first; if (v==up[u][0]) continue;
        up[v][0]=u; d[v]=d[u]+1; h[v]=h[u] + p.second;

        for (int j=1;j<=20;j++) up[v][j]=up[up[v][j-1]][j-1];
        dfs(v);

    }
}
int lca(int u, int v)
{
    if (d[u]!=d[v])
    {
        if (d[u] < d[v]) swap(u, v);
        int k=d[u]-d[v];
        for (int j=0;(1<<j) <= k;j++)
            if ((k>>j) & 1) u=up[u][j];
    }
    if (u==v) return u;
    int k=__lg(d[u]);
    for (int j=k;j>=0;j--)
        if (up[u][j]!=up[v][j]) u=up[u][j], v=up[v][j];
    return up[u][0];
}
bool uni(int u, int v, int x)
{
    if (lca(v, edge[x].second) != edge[x].second && lca(u, edge[x].second) != edge[x].second) return 1;
    if (lca(v, edge[x].second) == edge[x].second && lca(u, edge[x].second) == edge[x].second) return 1;
    return 0;
}
int main()
{
    //freopen(file".inp", "r", stdin);
    //freopen(file".out", "w", stdout);
    ios_base::sync_with_stdio(0); cin.tie(0);

    cin>>n>>s>>q>>H;
    for (int i=1;i<n;i++)
    {
        int u,v,w; cin>>u>>v>>w; E[u].pb({v, w}); E[v].pb({u, w}); edge.pb({u, v});
    }
    for (int i=1;i<=s;i++) {int x; cin>>x; a[x]=1;}

    h[0]=INT_MAX; dfs(1);
    for (int i=0;i<edge.size();i++)
        if (d[edge[i].first] > d[edge[i].second]) swap(edge[i].first, edge[i].second);

    while (q--)
    {
        int x,u; cin>>x>>u; x--;
        if (uni(u,H,x)) {cout<<"escaped\n"; continue;}

        long long res=INT_MAX;
        if (a[u]) {cout<<"0\n"; continue;}
        for (int i=1;i<=n;i++) if (a[i] && uni(i, u, x)) res=min(res, h[u]+h[i]-2*h[lca(i,u)]);

        if (res<INT_MAX) cout<<res<<'\n'; else cout<<"oo\n";
    }


}

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

valley.cpp: In function 'int main()':
valley.cpp:61:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     for (int i=0;i<edge.size();i++)
      |                  ~^~~~~~~~~~~~

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