oj.uz

답안 #556017

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
556017 2022-05-02T07:34:24 Z 600Mihnea Sprinkler (JOI22_sprinkler) C++17
9 / 100
 4000 ms 132424 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 37844 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

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

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

Subtask #4
0 / 12.0

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

Subtask #5
0 / 30.0

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

Subtask #6
0 / 17.0

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