oj.uz

답안 #533046

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
533046 2022-03-04T14:45:14 Z MinhAnhnd Regions (IOI09_regions) C++14
0 / 100
 8000 ms 23628 KB 
#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.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 8086 ms 5056 KB Time limit exceeded
2 Execution timed out 78 ms 5108 KB Time limit exceeded (wall clock)
3 Execution timed out 81 ms 5144 KB Time limit exceeded (wall clock)
4 Execution timed out 78 ms 5160 KB Time limit exceeded (wall clock)
5 Execution timed out 77 ms 5180 KB Time limit exceeded (wall clock)
6 Execution timed out 80 ms 5164 KB Time limit exceeded (wall clock)
7 Execution timed out 83 ms 5276 KB Time limit exceeded (wall clock)
8 Execution timed out 79 ms 5192 KB Time limit exceeded (wall clock)
9 Execution timed out 81 ms 5596 KB Time limit exceeded (wall clock)
10 Execution timed out 82 ms 5568 KB Time limit exceeded (wall clock)
11 Execution timed out 85 ms 5832 KB Time limit exceeded (wall clock)
12 Execution timed out 89 ms 6204 KB Time limit exceeded (wall clock)
13 Execution timed out 90 ms 5948 KB Time limit exceeded (wall clock)
14 Execution timed out 99 ms 6536 KB Time limit exceeded (wall clock)
15 Execution timed out 8022 ms 8900 KB Time limit exceeded

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 8052 ms 9200 KB Time limit exceeded
2 Execution timed out 8013 ms 8160 KB Time limit exceeded
3 Execution timed out 8032 ms 10924 KB Time limit exceeded
4 Execution timed out 95 ms 6468 KB Time limit exceeded (wall clock)
5 Execution timed out 97 ms 8124 KB Time limit exceeded (wall clock)
6 Execution timed out 109 ms 7632 KB Time limit exceeded (wall clock)
7 Execution timed out 123 ms 8380 KB Time limit exceeded (wall clock)
8 Execution timed out 135 ms 13108 KB Time limit exceeded (wall clock)
9 Execution timed out 178 ms 12892 KB Time limit exceeded (wall clock)
10 Execution timed out 193 ms 17452 KB Time limit exceeded (wall clock)
11 Execution timed out 221 ms 12620 KB Time limit exceeded (wall clock)
12 Execution timed out 214 ms 14212 KB Time limit exceeded (wall clock)
13 Execution timed out 239 ms 14604 KB Time limit exceeded (wall clock)
14 Execution timed out 222 ms 14060 KB Time limit exceeded (wall clock)
15 Execution timed out 262 ms 17956 KB Time limit exceeded (wall clock)
16 Execution timed out 199 ms 23628 KB Time limit exceeded (wall clock)
17 Execution timed out 201 ms 22428 KB Time limit exceeded (wall clock)