Submission #1271614

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271614		k12_khoi	Valley (BOI19_valley)	C++17	59 / 100	3095 ms	24944 KiB

valley

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<ll,int>
#define X first
#define Y second

const int N=1e5+5;
const int K=22;
const ll oo=(long double)1e18+1;

int n,request,s,e,banned,x,y,z;
int a[N],b[N],c[N];
ll d[N];
bool HaveShop[N];
vector <pii> adj[N];

namespace sub2
{
    ll res;
    priority_queue <pii,vector<pii>,greater<pii>> pq;

    void dijkstra(int u,int banned)
    {
        while (!pq.empty()) pq.pop();

        ll dist;

        for (int i=1;i<=n;i++)
        d[i]=oo;

        d[u]=0;
        pq.push(make_pair(0,u));

        while (!pq.empty())
        {
            dist=pq.top().X;
            u=pq.top().Y;
            pq.pop();

            if (dist>d[u]) continue;

            if (u==e)
            {
                cout << "escaped" << '\n';
                return;
            }

            for (pii v:adj[u])
            if (v.Y!=banned and d[v.X]>dist+c[v.Y])
            {
                d[v.X]=dist+c[v.Y];
                pq.push(make_pair(d[v.X],v.X));
            }
        }

        res=oo;
        for (int i=1;i<=n;i++)
        if (HaveShop[i]) res=min(res,d[i]);

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

    void solve()
    {
        while (request--)
        {
            cin >> banned >> x;
            dijkstra(x,banned);
        }
    }
}

namespace sub3
{
    int h;
    int H[N],p[N][K];
    bool check_E[N];

    void pre_dfs(int u,int root)
    {
        check_E[u]=(u==e);

        for (pii v:adj[u])
        if (v.Y!=root)
        {
            H[v.X]=H[u]+1;
            p[v.X][0]=u;

            pre_dfs(v.X,v.Y);

            check_E[u]|=check_E[v.X];
        }
    }

    int lca(int a,int b)
    {
        if (H[a]<H[b]) swap(a,b);

        for (int j=h;j>=0;j--)
        if (H[p[a][j]]>=H[b])
        {
            a=p[a][j];
        }

        if (a==b) return a;

        for (int j=h;j>=0;j--)
        if (p[a][j]!=p[b][j])
        {
            a=p[a][j];
            b=p[b][j];
        }

        return p[a][0];
    }

    void solve()
    {
        H[1]=1;
        pre_dfs(1,-1);

        for (int i=1;i<n;i++)
        if (H[a[i]]>H[b[i]]) swap(a[i],b[i]);

        h=31-__builtin_clz(n);

        for (int j=1;j<=h;j++)
        for (int i=1;i<=n;i++)
        p[i][j]=p[p[i][j-1]][j-1];

        while (request--)
        {
            cin >> banned >> x;

            if (lca(x,b[banned])==b[banned])
            {
                if (check_E[b[banned]]) cout << "escaped" << '\n';
                else cout << 0 << '\n';
            }
            else
            {
                if (check_E[b[banned]]==false) cout << "escaped" << '\n';
                else cout << 0 << '\n';
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n >> s >> request >> e;
    for (int i=1;i<n;i++)
    {
        cin >> a[i] >> b[i] >> c[i];
        adj[a[i]].push_back(make_pair(b[i],i));
        adj[b[i]].push_back(make_pair(a[i],i));
    }

    for (int i=1;i<=s;i++)
    {
        cin >> x;
        HaveShop[x]=true;
    }

    if (s==n) sub3::solve();
    else sub2::solve();
}

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