oj.uz

답안 #390683

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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