제출 #533046

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
533046		MinhAnhnd	Regions (IOI09_regions)	C++14	0 / 100	8086 ms	23628 KiB

regions

#include <bits/stdc++.h>
#include <iostream>
#define ll long long
#define ull unsigned ll
using namespace std;

    unsigned long long prime[25001];
    long par[200001];
    long country[200001];
    vector<long> child[200001];
    unsigned long long dp[25001]={};

ull dfs(long u){
    ull result = 1;
    for (auto v:child[u]){
        result*=dfs(v);
    }
    if (dp[country[u]] ==0){
        dp[country[u]] = result;
    }
    else {
        dp[country[u]] *=result;
    }
    result*=prime[country[u]];
    return result;
}

int main(){

    long j = 2;
    for (long i = 1;i<=25000;i++){
        bool o = false;
        do
        {
        o = false;
        for (long k = 2;k*k<=j;k++){
            if (j%k == 0){
                j++;
                o = true;
                break;
            }
        }
        } while (o);

        prime[i] = (unsigned long long) j;
        j++;
    }

    long N,R,Q;
    cin>>N>>R>>Q;
    cin>>country[1];
    for(long i = 2;i<=N;i++){
        cin>>par[i];
        child[par[i]].push_back(i);
        cin>>country[i];
    }

    dfs(1);

    for (long i = 1;i<=Q;i++){
        ull j,k,answer = 0;
        cin>>j>>k;
        ull temp = dp[j];
        ull divider = prime[k];
        while (temp%divider == 0){
            answer++;
            temp/=divider;
        }
        cout<<answer<<flush;
    }
  return 0;
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 85