Submission #898803

#	Time	Username	Problem	Language	Result	Execution time	Memory
898803		vjudge1	Valley (BOI19_valley)	C++17	59 / 100	3065 ms	20928 KiB

valley

#include <bits/stdc++.h>
#define pb push_back
#define f first
#define s second
#define dbg(x) cout << "reached here " << x << endl;
#define int long long 

using namespace std;
typedef pair<int, int> pii;

struct edge {int o, d, w, id;};

const int maxn = 1e5+5, inf = (int)100000*100000*100000;
int dis[maxn], E, st[maxn], ft[maxn], t = 1;
vector<edge> adj[maxn];
bool vis, mark[maxn];
vector<int> vec;
edge yal[maxn];

void dfs(int v, int par)
{
    st[v] = t;
    t++;
    for (auto e: adj[v])
    {
        int u = e.o^e.d^v;
        if(u != par)
        {
            dis[u] = dis[v] + 1;
            dfs(u, v);
        }
    }
    ft[v] = t;
    t++;
}

void dfs1(int v)
{
    if(v == E)
        vis = true;
    for (auto e: adj[v])
    {
        int u = e.o^e.d^v;
        if(!mark[e.id])
        {
            dis[u] = dis[v] + e.w;
            mark[e.id] = true;
            dfs1(u);
        }
    }
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, s, q;
    cin >> n >> s >> q >> E;

    for (int i = 1; i <= n-1; ++i)
    {
        cin >> yal[i].o >> yal[i].d >> yal[i].w;
        yal[i].id = i;

        adj[yal[i].o].pb(yal[i]);
        adj[yal[i].d].pb(yal[i]);
    }

    
    for (int i = 1; i <= s; ++i)
    {
        int a;
        cin >> a;
        vec.pb(a);
    }

    if(s == n)
    {
        dfs(E, 0);

        while(q--)
        {
            int l, r;
            cin >> l >> r;

            int v = yal[l].o;
            if(dis[yal[l].o] < dis[yal[l].d])
                v = yal[l].d;

            if(st[r] >= st[v] and ft[r] <= ft[v])
                cout << 0 << endl;
            else
                cout << "escaped" << endl;            
        }
    }

    else
    {
        while(q--)
        {
            int l, r;
            cin >> l >> r;
        
            for (int i = 1; i <= n; ++i)
            {
                dis[i] = -1;
                mark[i] = false;
            }
        
            dis[r] = 0;
            mark[l] = true;
            vis = false;
            dfs1(r);

            if(vis)
                cout << "escaped" << endl;
            else
            {
                int ans = inf;
                for (int i = 0; i < vec.size(); ++i)
                    if(dis[vec[i]] > -1)
                        ans = min(ans, dis[vec[i]]);

                if(ans != inf)
                    cout << ans << endl;
                else
                    cout << "oo" << endl;
            }
        }
    }

    return 0;
}

Compilation message (stderr)

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

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