Submission #898779

#	Time	Username	Problem	Language	Result	Execution time	Memory
898779		vjudge1	Valley (BOI19_valley)	C++17	36 / 100	3018 ms	13892 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;
bool vis, mark[maxn];
int dis[maxn], E;
vector<int> vec;
vector<edge> adj[maxn];

void dfs(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;
            dfs(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)
    {
        edge e;
        cin >> e.o >> e.d >> e.w;
        e.id = i;

        adj[e.o].pb(e);
        adj[e.d].pb(e);
    }

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

    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;
        dfs(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:82:31: 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]
   82 |             for (int i = 0; i < vec.size(); ++i)
      |                             ~~^~~~~~~~~~~~

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