oj.uz

Submission #390683

# Submission time Handle Problem Language Result Execution time Memory
390683 2021-04-16T13:58:32 Z cadmiumsky Fountain (eJOI20_fountain) C++14
100 / 100
 885 ms 24176 KB 
#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

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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2656 KB Output is correct
2 Correct 5 ms 2636 KB Output is correct
3 Correct 6 ms 2764 KB Output is correct
4 Correct 7 ms 2764 KB Output is correct
5 Correct 8 ms 2764 KB Output is correct
6 Correct 8 ms 2764 KB Output is correct
7 Correct 7 ms 2792 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 546 ms 21820 KB Output is correct
2 Correct 612 ms 20912 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2656 KB Output is correct
2 Correct 5 ms 2636 KB Output is correct
3 Correct 6 ms 2764 KB Output is correct
4 Correct 7 ms 2764 KB Output is correct
5 Correct 8 ms 2764 KB Output is correct
6 Correct 8 ms 2764 KB Output is correct
7 Correct 7 ms 2792 KB Output is correct
8 Correct 546 ms 21820 KB Output is correct
9 Correct 612 ms 20912 KB Output is correct
10 Correct 7 ms 2764 KB Output is correct
11 Correct 297 ms 11192 KB Output is correct
12 Correct 885 ms 24176 KB Output is correct
13 Correct 694 ms 18520 KB Output is correct
14 Correct 642 ms 16868 KB Output is correct
15 Correct 542 ms 15784 KB Output is correct