oj.uz

답안 #556019

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
556019 2022-05-02T07:45:21 Z 600Mihnea Sprinkler (JOI22_sprinkler) C++17
21 / 100
 2409 ms 140304 KB 
#include <bits/stdc++.h>

bool home = 1;

using namespace std;

typedef long long ll;
const int N=200000+7;
const int K=20;
int n;
int q;
int mod;
int h[N];
vector<int> g[N];
pair<int, int> rmq[K][2*N];
int lg[2*N];
int par[N];
int dep[N];
int first_euler[N];
int last_euler[N];
vector<int> la[N];
int top;
int verts[N];
int pos[N];

void build(int a,int p=-1){
  par[a]=p;
  la[dep[a]].push_back(a);
  rmq[0][++top]={dep[a], a};
  first_euler[a]=last_euler[a]=top;
  for(auto&b:g[a]){
    if(b==p) continue;
    dep[b]=1+dep[a];
    build(b,a);
    rmq[0][++top]={dep[a], a};
    last_euler[a]=top;
  }

}

int get_lca(int a,int b){
  if(first_euler[a]>last_euler[b]) swap(a,b);
  a=first_euler[a];
  b=last_euler[b];
  assert(a<=b);
  int k=lg[b-a+1];
  return min(rmq[k][a],rmq[k][b-(1<<k)+1]).second;
}

int get_dist(int a,int b){
  int c=get_lca(a,b);
  return dep[a]+dep[b]-2*dep[c];
}

int cnt_at_dep_before(int dep,int when) {
  int low=0,high=(int)la[dep].size()-1,sol=0;
  while(low<=high){
    int mid=(low+high)/2;
    if(first_euler[la[dep][mid]]<=when){
      sol=mid+1;
      low=mid+1;
    }else{
      high=mid-1;
    }
  }
  return sol;
}

int delta[N];
const int MX=40;

int mlt[N][MX+1];

void mulup(int &a,int b){
  assert(0<=a&&a<mod);
  assert(0<=b&&b<mod);
  a=a*(ll)b%mod;
}

signed main() {
#ifdef ONLINE_JUDGE
  home = 0;
#endif

  for(int i=0;i<N;i++){
    for(int j=0;j<=MX;j++){
      mlt[i][j]=1;
    }
  }

  home=0;

  if (home) {
    freopen("I_am_iron_man", "r", stdin);
  }
  else {
    ios::sync_with_stdio(0); cin.tie(0);
  }

  cin>>n>>mod;

  for (int i=1;i<n;i++) {
    int a, b;
    cin>>a>>b;
    g[a].push_back(b);
    g[b].push_back(a);
  }

  build(1);
  for(int i=2;i<=top;i++) lg[i]=1+lg[i/2];

  for (int k=1;(1<<k)<=top;k++) {
    for(int i=1;i+(1<<k)-1<=top;i++){
      rmq[k][i]=min(rmq[k-1][i],rmq[k-1][i+(1<<(k-1))]);
    }
  }
  {
    top=0;
    for (int d=0;d<=n;d++){
      delta[d]=top;
      for(auto &i:la[d]){
        verts[++top]=i;
        pos[i]=top;
      }
    }
    assert(top==n);
  }
  for (int i=1;i<=n;i++) {
    cin>>h[pos[i]];
  }
  cin>>q;
  while(q--){
    int type;
    cin>>type;
    assert(type==1||type==2);
    if(type==1){
      int x,d,w;
      cin>>x>>d>>w;

      vector<pair<int, int>> prs;

      int vertex=x;

      while (vertex>=1&&d>=0) {
        prs.push_back({vertex, d});
        vertex=par[vertex];
        d--;
      }

      reverse(prs.begin(),prs.end());

      int maxdep=-1;

      for (auto &it:prs){
        vertex=it.first;
        d=it.second;
        for(int h=dep[vertex];h<=dep[vertex]+d;h++){
          if(h>=maxdep){
            maxdep=h;
            mulup(mlt[vertex][h-dep[vertex]],w);
          }
        }
      }

    }else{
      int x,xinit;
      cin>>x;
      int sol=h[pos[x]];
      int cur_dist=0;
      while (x>=1&&cur_dist<=MX){
        sol=sol*(ll)mlt[x][cur_dist]%mod;
        x=par[x];
        cur_dist++;
      }

      cout<<sol<<"\n";
    }
  }


}

Compilation message

sprinkler.cpp: In function 'int main()':
sprinkler.cpp:166:13: warning: unused variable 'xinit' [-Wunused-variable]
  166 |       int x,xinit;
      |             ^~~~~
sprinkler.cpp:94:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |     freopen("I_am_iron_man", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 41812 KB Output is correct
2 Correct 20 ms 41828 KB Output is correct
3 Correct 21 ms 41928 KB Output is correct
4 Incorrect 25 ms 42124 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 41812 KB Output is correct
2 Correct 566 ms 116492 KB Output is correct
3 Correct 429 ms 113148 KB Output is correct
4 Correct 577 ms 127516 KB Output is correct
5 Correct 500 ms 114744 KB Output is correct
6 Correct 394 ms 114596 KB Output is correct
7 Correct 375 ms 114948 KB Output is correct
8 Correct 316 ms 115028 KB Output is correct
9 Correct 629 ms 136284 KB Output is correct
10 Correct 449 ms 131532 KB Output is correct
11 Correct 568 ms 116292 KB Output is correct
12 Correct 424 ms 113064 KB Output is correct
13 Correct 302 ms 114292 KB Output is correct
14 Correct 315 ms 113820 KB Output is correct
15 Correct 299 ms 113484 KB Output is correct
16 Correct 307 ms 113552 KB Output is correct
17 Correct 333 ms 113912 KB Output is correct
18 Correct 22 ms 41864 KB Output is correct
19 Correct 22 ms 41880 KB Output is correct
20 Correct 21 ms 41812 KB Output is correct
21 Correct 23 ms 41812 KB Output is correct
22 Correct 22 ms 41880 KB Output is correct

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 41812 KB Output is correct
2 Correct 566 ms 116492 KB Output is correct
3 Correct 429 ms 113148 KB Output is correct
4 Correct 577 ms 127516 KB Output is correct
5 Correct 500 ms 114744 KB Output is correct
6 Correct 394 ms 114596 KB Output is correct
7 Correct 375 ms 114948 KB Output is correct
8 Correct 316 ms 115028 KB Output is correct
9 Correct 629 ms 136284 KB Output is correct
10 Correct 449 ms 131532 KB Output is correct
11 Correct 568 ms 116292 KB Output is correct
12 Correct 424 ms 113064 KB Output is correct
13 Correct 302 ms 114292 KB Output is correct
14 Correct 315 ms 113820 KB Output is correct
15 Correct 299 ms 113484 KB Output is correct
16 Correct 307 ms 113552 KB Output is correct
17 Correct 333 ms 113912 KB Output is correct
18 Correct 22 ms 41864 KB Output is correct
19 Correct 22 ms 41880 KB Output is correct
20 Correct 21 ms 41812 KB Output is correct
21 Correct 23 ms 41812 KB Output is correct
22 Correct 22 ms 41880 KB Output is correct
23 Correct 26 ms 41888 KB Output is correct
24 Incorrect 626 ms 124252 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 41812 KB Output is correct
2 Correct 927 ms 140304 KB Output is correct
3 Correct 2409 ms 135764 KB Output is correct
4 Correct 1016 ms 136612 KB Output is correct
5 Correct 831 ms 121180 KB Output is correct
6 Correct 571 ms 120980 KB Output is correct
7 Correct 512 ms 121076 KB Output is correct
8 Correct 345 ms 121140 KB Output is correct
9 Correct 855 ms 134712 KB Output is correct
10 Correct 2376 ms 139412 KB Output is correct
11 Correct 749 ms 121012 KB Output is correct
12 Correct 1710 ms 121576 KB Output is correct
13 Correct 1094 ms 122064 KB Output is correct
14 Correct 1156 ms 123348 KB Output is correct
15 Correct 22 ms 41940 KB Output is correct
16 Correct 24 ms 41804 KB Output is correct
17 Correct 22 ms 41856 KB Output is correct
18 Correct 22 ms 41904 KB Output is correct
19 Correct 22 ms 41824 KB Output is correct

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 41768 KB Output is correct
2 Incorrect 894 ms 130812 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 41812 KB Output is correct
2 Correct 20 ms 41828 KB Output is correct
3 Correct 21 ms 41928 KB Output is correct
4 Incorrect 25 ms 42124 KB Output isn't correct
5 Halted 0 ms 0 KB -