Submission #928923

#	Time	Username	Problem	Language	Result	Execution time	Memory
928923		Faisal_Saqib	Valley (BOI19_valley)	C++17	59 / 100	3101 ms	29896 KiB

valley

#include <iostream>
#include <vector>
#include <set>
#include <queue>
using namespace std;
const int N=1e5+10;
pair<int,int> qp[N];
pair<int,int> ed[N];
vector<pair<int,int>> ma[N],query[N],adj[N];
int ans[N],shop[N];
long long dist[N];
set<int> cur;
void dfs(int x,int p=-1)
{
  for(auto [ind,bl]:query[x])
    if(cur.find(bl)==cur.end())
      ans[ind]=1;
  for(auto [y,ind]:ma[x])
  {
    if(y!=p)
    {
    cur.insert(ind);
      dfs(y,x);
    cur.erase(ind);
    }
  }
}
int main()
{
  int n,s,q,e;
  cin>>n>>s>>q>>e;
  // n is Number of villages
  // s is number of villages with shops
  // q is queries
  // e is the exit village
  for(int i=1;i<n;i++)
  {
    int a,b,w;
    cin>>a>>b>>w;
    ed[i].first=a;
    ed[i].second=b;
    ma[a].push_back({b,i});
    adj[a].push_back({b,w});
    // Edge between a and b with length w
    ma[b].push_back({a,i});
    adj[b].push_back({a,w});
  }
  int sp;
  for(int i=0;i<s;i++)
  {
  cin>>sp;
  shop[sp]=1;
  }
  for(int i=0;i<q;i++)
  {
    int r,l;
    cin>>r>>l;
    qp[i]={l,r};
    query[l].push_back({i,r});
   }
   dfs(e);
   for(int j=0;j<q;j++)
   {
     if(ans[j])
     {
      cout<<"escaped\n";
     }
     else if(shop[qp[j].first])
     {
      cout<<0<<endl;
     }
     else
     {
        for(int i=1;i<=n;i++)
          dist[i]=1e17;
        long long anp=1e17;
        int sv=qp[j].first;
        int ca=ed[qp[j].second].first;
        int cb=ed[qp[j].second].second;
        dist[sv]=0;
        bool lp=0;
        priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int>>> pq;
        pq.push({dist[sv],sv});
        while(pq.size())
        {
          auto it =pq.top();
          pq.pop();
          if(shop[it.second])
          {
            lp=1;
            cout<<it.first<<endl;
            break;
          }
          if(dist[it.second]==it.first)
          {
            for(auto [nv,ew]:adj[it.second])
            {
              if((nv==ca and it.second==cb) or (nv==cb and it.second==ca))
                continue;
              if(dist[nv]>(it.first+(long long)ew))
              {
                dist[nv]=it.first+(long long)ew;
                pq.push({dist[nv],nv});
              }
            }
          }
        }
        if(!lp)
          cout<<"oo\n";
     }
   }
  return 0;
}

Compilation message (stderr)

valley.cpp: In function 'int main()':
valley.cpp:76:19: warning: unused variable 'anp' [-Wunused-variable]
   76 |         long long anp=1e17;
      |                   ^~~

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