Submission #555999

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
555999	2022-05-02T06:52:31 Z	600Mihnea	Sprinkler (JOI22_sprinkler)	C++17	9 / 100	4000 ms	132288 KB

sprinkler

#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 mod_phi;
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];

vector<pair<int, int>> factorize(int n){
  vector<pair<int, int>> sol;
  for(int d=2;d*d<=n;d++){
    int e=0;
    while(n%d==0) n/=d, e++;
    if(e) sol.push_back({d, e});
  }
  if(n>1){
    sol.push_back({n, 1});
  }
  return sol;
}

int pwmod(int a,int b){
  assert(0<=a&&a<mod);
  int r=1;
  while (b) {
    if (b&1) r=r*(ll)a%mod;
    a=a*(ll)a%mod;
    b/=2;
  }
  return r;
}

int y;

const int MX=2;

struct T {
  int w=1; /// coprime with mod
  int e[11];
};

T mlt[N][MX+1];

void mulup(T&a,T&b){
  a.w=a.w*(ll)b.w%mod;
  for (int i=0;i<y;i++){
    a.e[i]+=b.e[i];
  }
}

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;
  vector<pair<int, int>> mod_factors=factorize(mod);

  mod_phi=mod;

  for (auto &it:mod_factors){
    if(mod_phi%it.first==0) mod_phi/=it.first, mod_phi*=(it.first-1);
  }

  y=(int)mod_factors.size();

  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<int> cnt_divi_w(y);
      for (int i=0;i<y;i++){
        while(w%mod_factors[i].first==0) {
          w/=mod_factors[i].first;
          cnt_divi_w[i]++;
        }
      }
      int winv=pwmod(w,mod_phi-1);
      assert(w*(ll)winv%mod==1);

      T t;
      T tinv;
      t.w=w;
      tinv.w=winv;
      for (int i=0;i<y;i++){
        t.e[i]=cnt_divi_w[i];
        tinv.e[i]=-cnt_divi_w[i];
      }

      int vertex=x,ant;

      while (vertex>=1&&d>=0) {
        mulup(mlt[vertex][d],t);
        if(vertex!=x){
          if (d-1>=0){
            mulup(mlt[ant][d-1],tinv);
          }
        }
        ant=vertex;
        vertex=par[vertex];
        d--;
      }
    }else{
      int x,xinit;
      cin>>x;
      xinit=x;
      T cur;
      cur.w=1;
      for(int i=0;i<y;i++){
        cur.e[i]=0;
      }
      int cur_dist=0;
      while (x>=1&&cur_dist<=MX){
        for (int i=cur_dist;i<=MX;i++){
          mulup(cur,mlt[x][i]);
        }
        x=par[x];
        cur_dist++;
      }
      x=xinit;
      int sol=h[pos[x]];
      sol=sol*(ll)cur.w%mod;
      for (int i=0;i<y;i++){
        if(cur.e[i]) {
          sol=sol*(ll)pwmod(mod_factors[i].first,cur.e[i])%mod;
        }
      }
      cout<<sol<<"\n";
    }
  }


}

Compilation message

sprinkler.cpp: In function 'int main()':
sprinkler.cpp:122:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |     freopen("I_am_iron_man", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sprinkler.cpp:108:6: warning: 'ant' may be used uninitialized in this function [-Wmaybe-uninitialized]
  108 |   a.w=a.w*(ll)b.w%mod;
      |   ~~~^~~~~~~~~~~~~~~~
sprinkler.cpp:195:20: note: 'ant' was declared here
  195 |       int vertex=x,ant;
      |                    ^~~

Subtask #1
0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	17 ms	37932 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	37936 KB	Output is correct
2	Correct	486 ms	112372 KB	Output is correct
3	Correct	651 ms	109228 KB	Output is correct
4	Correct	508 ms	123416 KB	Output is correct
5	Correct	480 ms	110632 KB	Output is correct
6	Correct	435 ms	110568 KB	Output is correct
7	Correct	486 ms	110720 KB	Output is correct
8	Correct	384 ms	111204 KB	Output is correct
9	Correct	471 ms	132288 KB	Output is correct
10	Correct	526 ms	127304 KB	Output is correct
11	Correct	403 ms	112272 KB	Output is correct
12	Correct	501 ms	109048 KB	Output is correct
13	Correct	461 ms	110192 KB	Output is correct
14	Correct	468 ms	109808 KB	Output is correct
15	Correct	438 ms	109500 KB	Output is correct
16	Correct	498 ms	109512 KB	Output is correct
17	Correct	478 ms	110216 KB	Output is correct
18	Correct	18 ms	37868 KB	Output is correct
19	Correct	20 ms	37972 KB	Output is correct
20	Correct	17 ms	37884 KB	Output is correct
21	Correct	18 ms	37948 KB	Output is correct
22	Correct	18 ms	37908 KB	Output is correct

Subtask #3
0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	37936 KB	Output is correct
2	Correct	486 ms	112372 KB	Output is correct
3	Correct	651 ms	109228 KB	Output is correct
4	Correct	508 ms	123416 KB	Output is correct
5	Correct	480 ms	110632 KB	Output is correct
6	Correct	435 ms	110568 KB	Output is correct
7	Correct	486 ms	110720 KB	Output is correct
8	Correct	384 ms	111204 KB	Output is correct
9	Correct	471 ms	132288 KB	Output is correct
10	Correct	526 ms	127304 KB	Output is correct
11	Correct	403 ms	112272 KB	Output is correct
12	Correct	501 ms	109048 KB	Output is correct
13	Correct	461 ms	110192 KB	Output is correct
14	Correct	468 ms	109808 KB	Output is correct
15	Correct	438 ms	109500 KB	Output is correct
16	Correct	498 ms	109512 KB	Output is correct
17	Correct	478 ms	110216 KB	Output is correct
18	Correct	18 ms	37868 KB	Output is correct
19	Correct	20 ms	37972 KB	Output is correct
20	Correct	17 ms	37884 KB	Output is correct
21	Correct	18 ms	37948 KB	Output is correct
22	Correct	18 ms	37908 KB	Output is correct
23	Execution timed out	4083 ms	37904 KB	Time limit exceeded
24	Halted	0 ms	0 KB	-