Submission #556017

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
556017	2022-05-02T07:34:24 Z	600Mihnea	Sprinkler (JOI22_sprinkler)	C++17	9 / 100	4000 ms	132424 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	37844 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	16 ms	37856 KB	Output is correct
2	Correct	523 ms	112348 KB	Output is correct
3	Correct	636 ms	109368 KB	Output is correct
4	Correct	508 ms	123640 KB	Output is correct
5	Correct	476 ms	111004 KB	Output is correct
6	Correct	475 ms	110592 KB	Output is correct
7	Correct	491 ms	110920 KB	Output is correct
8	Correct	411 ms	111224 KB	Output is correct
9	Correct	455 ms	132424 KB	Output is correct
10	Correct	569 ms	127556 KB	Output is correct
11	Correct	443 ms	112416 KB	Output is correct
12	Correct	554 ms	109400 KB	Output is correct
13	Correct	483 ms	110268 KB	Output is correct
14	Correct	509 ms	110036 KB	Output is correct
15	Correct	450 ms	109876 KB	Output is correct
16	Correct	507 ms	109768 KB	Output is correct
17	Correct	502 ms	110272 KB	Output is correct
18	Correct	18 ms	37972 KB	Output is correct
19	Correct	19 ms	37972 KB	Output is correct
20	Correct	18 ms	37888 KB	Output is correct
21	Correct	18 ms	37972 KB	Output is correct
22	Correct	17 ms	38004 KB	Output is correct

Subtask #3
0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	37856 KB	Output is correct
2	Correct	523 ms	112348 KB	Output is correct
3	Correct	636 ms	109368 KB	Output is correct
4	Correct	508 ms	123640 KB	Output is correct
5	Correct	476 ms	111004 KB	Output is correct
6	Correct	475 ms	110592 KB	Output is correct
7	Correct	491 ms	110920 KB	Output is correct
8	Correct	411 ms	111224 KB	Output is correct
9	Correct	455 ms	132424 KB	Output is correct
10	Correct	569 ms	127556 KB	Output is correct
11	Correct	443 ms	112416 KB	Output is correct
12	Correct	554 ms	109400 KB	Output is correct
13	Correct	483 ms	110268 KB	Output is correct
14	Correct	509 ms	110036 KB	Output is correct
15	Correct	450 ms	109876 KB	Output is correct
16	Correct	507 ms	109768 KB	Output is correct
17	Correct	502 ms	110272 KB	Output is correct
18	Correct	18 ms	37972 KB	Output is correct
19	Correct	19 ms	37972 KB	Output is correct
20	Correct	18 ms	37888 KB	Output is correct
21	Correct	18 ms	37972 KB	Output is correct
22	Correct	17 ms	38004 KB	Output is correct
23	Execution timed out	4067 ms	37908 KB	Time limit exceeded
24	Halted	0 ms	0 KB	-