oj.uz

답안 #555999

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
555999 2022-05-02T06:52:31 Z 600Mihnea Sprinkler (JOI22_sprinkler) C++17
9 / 100
 4000 ms 132288 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 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 17 ms 37932 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4054 ms 37972 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 17 ms 37916 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 17 ms 37932 KB Output isn't correct
2 Halted 0 ms 0 KB -