oj.uz

Submission #555891

# Submission time Handle Problem Language Result Execution time Memory
555891 2022-05-01T18:40:33 Z 600Mihnea Sprinkler (JOI22_sprinkler) C++17
3 / 100
 4000 ms 89096 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 dep[N];
int first_euler[N];
int last_euler[N];
int top;
int ord[N];
int low[N];
int high[N];
int tt;

void build(int a,int p=-1){
  ord[++tt]=a;
  low[a]=tt;

  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;
  }

  high[a]=tt;
}

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];
}

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

  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))]);
    }
  }

  for (int i=1;i<=n;i++) {
    cin>>h[low[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;
      for (int i=1;i<=n;i++){

        if(get_dist(x,ord[i])<=d){
          h[i]=h[i]*(ll)w%mod;
        }
      }
    }else{
      int x;
      cin>>x;
      cout<<h[low[x]]<<"\n";
    }
  }


}

Compilation message

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

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5076 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 4 ms 5040 KB Output is correct
4 Correct 12 ms 5332 KB Output is correct
5 Correct 10 ms 5304 KB Output is correct
6 Correct 11 ms 5332 KB Output is correct
7 Correct 9 ms 5412 KB Output is correct
8 Correct 10 ms 5332 KB Output is correct
9 Correct 5 ms 5076 KB Output is correct
10 Correct 3 ms 5048 KB Output is correct
11 Correct 3 ms 5040 KB Output is correct
12 Correct 3 ms 5060 KB Output is correct
13 Correct 4 ms 5040 KB Output is correct
14 Correct 3 ms 5076 KB Output is correct
15 Correct 5 ms 5076 KB Output is correct
16 Correct 4 ms 5076 KB Output is correct
17 Correct 4 ms 5076 KB Output is correct
18 Correct 3 ms 5076 KB Output is correct
19 Correct 5 ms 5044 KB Output is correct
20 Correct 4 ms 5040 KB Output is correct
21 Correct 4 ms 5076 KB Output is correct
22 Correct 3 ms 5076 KB Output is correct
23 Correct 3 ms 5076 KB Output is correct
24 Correct 3 ms 5076 KB Output is correct
25 Correct 3 ms 5036 KB Output is correct
26 Correct 5 ms 5076 KB Output is correct
27 Correct 4 ms 5056 KB Output is correct
28 Correct 4 ms 5076 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Execution timed out 4040 ms 74356 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Execution timed out 4040 ms 74356 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Execution timed out 4049 ms 89096 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5076 KB Output is correct
2 Execution timed out 4106 ms 84288 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5076 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 4 ms 5040 KB Output is correct
4 Correct 12 ms 5332 KB Output is correct
5 Correct 10 ms 5304 KB Output is correct
6 Correct 11 ms 5332 KB Output is correct
7 Correct 9 ms 5412 KB Output is correct
8 Correct 10 ms 5332 KB Output is correct
9 Correct 5 ms 5076 KB Output is correct
10 Correct 3 ms 5048 KB Output is correct
11 Correct 3 ms 5040 KB Output is correct
12 Correct 3 ms 5060 KB Output is correct
13 Correct 4 ms 5040 KB Output is correct
14 Correct 3 ms 5076 KB Output is correct
15 Correct 5 ms 5076 KB Output is correct
16 Correct 4 ms 5076 KB Output is correct
17 Correct 4 ms 5076 KB Output is correct
18 Correct 3 ms 5076 KB Output is correct
19 Correct 5 ms 5044 KB Output is correct
20 Correct 4 ms 5040 KB Output is correct
21 Correct 4 ms 5076 KB Output is correct
22 Correct 3 ms 5076 KB Output is correct
23 Correct 3 ms 5076 KB Output is correct
24 Correct 3 ms 5076 KB Output is correct
25 Correct 3 ms 5036 KB Output is correct
26 Correct 5 ms 5076 KB Output is correct
27 Correct 4 ms 5056 KB Output is correct
28 Correct 4 ms 5076 KB Output is correct
29 Correct 3 ms 5076 KB Output is correct
30 Execution timed out 4040 ms 74356 KB Time limit exceeded
31 Halted 0 ms 0 KB -