oj.uz

Submission #533036

# Submission time Handle Problem Language Result Execution time Memory
533036 2022-03-04T14:31:23 Z MinhAnhnd Regions (IOI09_regions) C++14
0 / 100
 8000 ms 23688 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++;
    }

    unsigned long long regions[25001];
    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;
    }
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:49:24: warning: unused variable 'regions' [-Wunused-variable]
   49 |     unsigned long long regions[25001];
      |                        ^~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8032 ms 5156 KB Time limit exceeded
2 Execution timed out 79 ms 5184 KB Time limit exceeded (wall clock)
3 Execution timed out 79 ms 5072 KB Time limit exceeded (wall clock)
4 Execution timed out 80 ms 5156 KB Time limit exceeded (wall clock)
5 Execution timed out 87 ms 5188 KB Time limit exceeded (wall clock)
6 Execution timed out 77 ms 5144 KB Time limit exceeded (wall clock)
7 Execution timed out 77 ms 5232 KB Time limit exceeded (wall clock)
8 Execution timed out 86 ms 5300 KB Time limit exceeded (wall clock)
9 Execution timed out 86 ms 5652 KB Time limit exceeded (wall clock)
10 Execution timed out 83 ms 5500 KB Time limit exceeded (wall clock)
11 Execution timed out 86 ms 5888 KB Time limit exceeded (wall clock)
12 Execution timed out 86 ms 6212 KB Time limit exceeded (wall clock)
13 Execution timed out 91 ms 5956 KB Time limit exceeded (wall clock)
14 Execution timed out 99 ms 6364 KB Time limit exceeded (wall clock)
15 Execution timed out 8013 ms 8892 KB Time limit exceeded

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8041 ms 9344 KB Time limit exceeded
2 Execution timed out 8092 ms 8216 KB Time limit exceeded
3 Execution timed out 8093 ms 11072 KB Time limit exceeded
4 Execution timed out 93 ms 6496 KB Time limit exceeded (wall clock)
5 Execution timed out 98 ms 8072 KB Time limit exceeded (wall clock)
6 Execution timed out 107 ms 7568 KB Time limit exceeded (wall clock)
7 Execution timed out 131 ms 8384 KB Time limit exceeded (wall clock)
8 Execution timed out 139 ms 13104 KB Time limit exceeded (wall clock)
9 Execution timed out 176 ms 12816 KB Time limit exceeded (wall clock)
10 Execution timed out 180 ms 17432 KB Time limit exceeded (wall clock)
11 Execution timed out 230 ms 12556 KB Time limit exceeded (wall clock)
12 Execution timed out 220 ms 14272 KB Time limit exceeded (wall clock)
13 Execution timed out 207 ms 14500 KB Time limit exceeded (wall clock)
14 Execution timed out 249 ms 14056 KB Time limit exceeded (wall clock)
15 Execution timed out 214 ms 17900 KB Time limit exceeded (wall clock)
16 Execution timed out 204 ms 23688 KB Time limit exceeded (wall clock)
17 Execution timed out 197 ms 22440 KB Time limit exceeded (wall clock)