oj.uz

답안 #555998

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

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 12 ms 28500 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 28500 KB Output is correct
2 Correct 410 ms 104304 KB Output is correct
3 Correct 587 ms 110784 KB Output is correct
4 Correct 489 ms 123208 KB Output is correct
5 Correct 498 ms 110748 KB Output is correct
6 Correct 423 ms 108424 KB Output is correct
7 Correct 454 ms 110688 KB Output is correct
8 Correct 383 ms 108896 KB Output is correct
9 Correct 424 ms 130860 KB Output is correct
10 Correct 535 ms 129024 KB Output is correct
11 Correct 427 ms 109260 KB Output is correct
12 Correct 521 ms 107852 KB Output is correct
13 Correct 479 ms 112228 KB Output is correct
14 Correct 475 ms 112092 KB Output is correct
15 Correct 437 ms 101496 KB Output is correct
16 Correct 511 ms 105972 KB Output is correct
17 Correct 483 ms 107232 KB Output is correct
18 Correct 13 ms 28500 KB Output is correct
19 Correct 14 ms 28532 KB Output is correct
20 Correct 14 ms 28484 KB Output is correct
21 Correct 17 ms 28500 KB Output is correct
22 Correct 15 ms 28500 KB Output is correct

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 28500 KB Output is correct
2 Correct 410 ms 104304 KB Output is correct
3 Correct 587 ms 110784 KB Output is correct
4 Correct 489 ms 123208 KB Output is correct
5 Correct 498 ms 110748 KB Output is correct
6 Correct 423 ms 108424 KB Output is correct
7 Correct 454 ms 110688 KB Output is correct
8 Correct 383 ms 108896 KB Output is correct
9 Correct 424 ms 130860 KB Output is correct
10 Correct 535 ms 129024 KB Output is correct
11 Correct 427 ms 109260 KB Output is correct
12 Correct 521 ms 107852 KB Output is correct
13 Correct 479 ms 112228 KB Output is correct
14 Correct 475 ms 112092 KB Output is correct
15 Correct 437 ms 101496 KB Output is correct
16 Correct 511 ms 105972 KB Output is correct
17 Correct 483 ms 107232 KB Output is correct
18 Correct 13 ms 28500 KB Output is correct
19 Correct 14 ms 28532 KB Output is correct
20 Correct 14 ms 28484 KB Output is correct
21 Correct 17 ms 28500 KB Output is correct
22 Correct 15 ms 28500 KB Output is correct
23 Execution timed out 4058 ms 28520 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

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

Subtask #5
0 / 30.0

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

Subtask #6
0 / 17.0

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