Submission #390683

#	Time	Username	Problem	Language	Result	Execution time	Memory
390683		cadmiumsky	Fountain (eJOI20_fountain)	C++14	100 / 100	885 ms	24176 KiB

fountain

#include <iostream>
#include <vector>

using namespace std;

vector<int> tree[100001];

int diam[100001],cap[100001];
int father[100001][18];
int stack[100001],spoz;
int nzbound[100001];

static void setcapa(int node, int b=-1) {
  nzbound[node]=b;
  //cout << cap[node] <<' ' << node << " capa\n"; 
  for(int child,i=0; i<tree[node].size();i++) {
    child=tree[node][i];
    cap[child]+=cap[node];
    setcapa(child,(b==-1?child:b));
  }
}

static inline int sum(int down,int up) {
  return cap[down]-cap[father[up][0]];
}

int main() {
  int n,q;
  cin >> n >> q;
  spoz=0;
  stack[0]=0;
  cap[0]=0;
  diam[0]=1000000001;
  for(int i=1,d,c; i<=n; i++) {
    cin >> d >> c;
    diam[i]=d;
    cap[i]=c;
  }
  for(int i=n,d; i>0; i--) {
    d=diam[i];
    //c=cap[i];
    while(diam[ stack[spoz] ]<=d)
      spoz--;
    father[i][0]=stack[spoz];
    //cout << i << ' '<< stack[spoz] <<'\n';
    tree[stack[spoz]].push_back(i);
    stack[++spoz]=i;
  }
  father[0][0]=0;
  for(int step=1; step<18; step++) {
    for(int i=0; i<=n; i++)
      father[i][step]=father[father[i][step-1]][step-1];
  }
  setcapa(0);
  for(int i=0,node,vol; i<q; i++) {
    cin >> node >> vol;
    //cout << node <<' ' << nzbound[node] <<' '<< sum(1,5) <<'\t';
    if(cap[node]<vol) {
      cout << "0\n";
      continue;
    }
    int currcapa=sum(node,node);
    if(currcapa>=vol) {
      cout << node << '\n';
      continue;
    }
    int bound=node,temp;
    for(int step=17; step>=0; step--) {
      temp=father[bound][step];
      if(temp==0)
        temp=nzbound[node];
      //cout <<"mama "<< node <<' ' << temp <<' ' << sum(node,temp) <<' '<< vol << '\n';
      if(sum(node,temp)<vol)
        bound=temp;
    } 
    cout <<  father[bound][0] << '\n';
  }
}

Compilation message (stderr)

fountain.cpp: In function 'void setcapa(int, int)':
fountain.cpp:16:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |   for(int child,i=0; i<tree[node].size();i++) {
      |                      ~^~~~~~~~~~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40