Submission #1327400

#TimeUsernameProblemLanguageResultExecution timeMemory
1327400lizaValley (BOI19_valley)C++20
59 / 100
3097 ms96652 KiB
#include <bits/stdc++.h>

using namespace std;

int n, s, q, e;
int const N = 100005;
vector<pair<int, int>> g[N];
vector <int> et;
pair<int, int> eti[N];
vector<int> shops;
pair<int, int> roads[N];
void fet(int u, int p)
{
    et.push_back(u);
    eti[u]={et.size()-1, 0};
    for(auto i: g[u])
    {
        if(i.first == p)continue;
        fet(i.first, u);
    }
    et.push_back(u);
    eti[u]={eti[u].first, et.size()-1};
}

set<pair<long long, int>> diss[N];
vector<pair<int, int>> qi;
map<int, int> isr;
map<int, int> iss;

void dis(int sak, int u, int p,  long long di=0, int deep=0)
{
    if(isr[u])
    {
        if(iss[u] && di!=0){}
        else
        diss[u].insert(make_pair(di, sak));
    }

    if(2e6/n-1 < diss[u].size())
    {
        diss[u].erase(prev(diss[u].end()));
    }
    for(auto i: g[u])
    {
        if(i.first == p)continue;
        dis(sak, i.first, u, di+i.second, deep+1);
    }
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> s >> q >> e;
    for(int i = 0; i < n-1; i++)
    {
        int a, b, w; cin >> a >> b >> w;
        g[a].push_back({b, w});
        g[b].push_back({a, w});
        roads[i+1]={a, b};
    }
    for(int i =0; i < s; i++)
    {
        int x; cin >> x;
        shops.push_back(x);
       // if(s!=n)dis(x, x, 0);
    }
    fet(e, 0);
    for(int i = 0; i < q; i++)
    {
        int a, b; cin >> a >> b;
        qi.push_back({a, b});
        isr[b]++;
    }

    for(int i =0; i < s; i++)
    {
        int x = shops[i];
        if(s!=n)dis(x, x, 0);
    }

    for(int jj = 0; jj < q; jj++)
    {
        int i, r; i=qi[jj].first;
        r =  qi[jj].second;
        if(eti[roads[i].first].first <= eti[r].first && eti[roads[i].second].first <= eti[r].first && eti[roads[i].first].second >= eti[r].second && eti[roads[i].second].second >= eti[r].second)
        {
            if(s==n)
            {
                cout << "0\n"; continue;
            }
            long long rez=-1;

            for(auto kk: diss[r])
            {
                int k = kk.second;
                if(eti[roads[i].first].first <= eti[k].first && eti[roads[i].second].first <= eti[k].first && eti[roads[i].first].second >= eti[k].second && eti[roads[i].second].second >= eti[k].second)
                {
                    rez=0;
                    cout << kk.first << "\n";
                    break;

                }
            }
            if(rez==-1)
            cout << "oo\n";
        }
        else
        {
            cout << "escaped\n";
        }
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...