oj.uz

Submission #555883

# Submission time Handle Problem Language Result Execution time Memory
555883 2022-05-01T18:36:23 Z 600Mihnea Sprinkler (JOI22_sprinkler) C++17
3 / 100
 4000 ms 90888 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[N];
int last[N];
int top;

void build(int a,int p=-1){
  rmq[0][++top]={dep[a], a};
  first[a]=last[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[a]=top;
  }
}

int get_lca(int a,int b){
  if(first[a]>last[b]) swap(a,b);
  a=first[a];
  b=last[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[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,i)<=d){
          h[i]=h[i]*(ll)w%mod;
        }
      }
    }else{
      int x;
      cin>>x;
      cout<<h[x]<<"\n";
    }
  }


}

Compilation message

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

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 2 ms 5076 KB Output is correct
3 Correct 2 ms 5040 KB Output is correct
4 Correct 9 ms 5332 KB Output is correct
5 Correct 12 ms 5376 KB Output is correct
6 Correct 11 ms 5332 KB Output is correct
7 Correct 9 ms 5332 KB Output is correct
8 Correct 8 ms 5384 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 3 ms 5040 KB Output is correct
11 Correct 3 ms 5076 KB Output is correct
12 Correct 3 ms 5040 KB Output is correct
13 Correct 3 ms 5076 KB Output is correct
14 Correct 3 ms 5076 KB Output is correct
15 Correct 4 ms 5076 KB Output is correct
16 Correct 3 ms 5076 KB Output is correct
17 Correct 3 ms 5040 KB Output is correct
18 Correct 3 ms 5036 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 3 ms 5036 KB Output is correct
21 Correct 3 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 5076 KB Output is correct
26 Correct 3 ms 5076 KB Output is correct
27 Correct 4 ms 5076 KB Output is correct
28 Correct 3 ms 5036 KB Output is correct

Subtask #2
0 / 9.0

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

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5076 KB Output is correct
2 Execution timed out 4083 ms 76236 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 4061 ms 90888 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

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

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 2 ms 5076 KB Output is correct
3 Correct 2 ms 5040 KB Output is correct
4 Correct 9 ms 5332 KB Output is correct
5 Correct 12 ms 5376 KB Output is correct
6 Correct 11 ms 5332 KB Output is correct
7 Correct 9 ms 5332 KB Output is correct
8 Correct 8 ms 5384 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 3 ms 5040 KB Output is correct
11 Correct 3 ms 5076 KB Output is correct
12 Correct 3 ms 5040 KB Output is correct
13 Correct 3 ms 5076 KB Output is correct
14 Correct 3 ms 5076 KB Output is correct
15 Correct 4 ms 5076 KB Output is correct
16 Correct 3 ms 5076 KB Output is correct
17 Correct 3 ms 5040 KB Output is correct
18 Correct 3 ms 5036 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 3 ms 5036 KB Output is correct
21 Correct 3 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 5076 KB Output is correct
26 Correct 3 ms 5076 KB Output is correct
27 Correct 4 ms 5076 KB Output is correct
28 Correct 3 ms 5036 KB Output is correct
29 Correct 2 ms 5076 KB Output is correct
30 Execution timed out 4083 ms 76236 KB Time limit exceeded
31 Halted 0 ms 0 KB -