Submission #927578

#	Time	Username	Problem	Language	Result	Execution time	Memory
927578		Faisal_Saqib	Valley (BOI19_valley)	C++17	23 / 100	223 ms	18040 KiB

valley

#include <iostream>
#include <vector>
#include <set>
using namespace std;
const int N=1e5+10;
vector<pair<int,int>> ma[N],query[N];
int ans[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;
    ma[a].push_back({b,i});
    // Edge between a and b with length w
    ma[b].push_back({a,i});
  }
  int sp;
  for(int i=0;i<s;i++)
    cin>>sp;
  for(int i=0;i<q;i++)
  {
    int r,l;
    cin>>r>>l;
    query[l].push_back({i,r});
   }
   dfs(e);
   for(int j=0;j<q;j++)
   {
      cout<<((ans[j])?"escaped\n":"0\n");
    }
  return 0;
}

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