oj.uz

Submission #852558

# Submission time Handle Problem Language Result Execution time Memory
852558 2023-09-22T05:33:02 Z abcvuitunggio Regions (IOI09_regions) C++17
0 / 100
 86 ms 131072 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int sz=158;
int n,R,q,r1,r2,cnt[200001][sz+1],c[25001][sz+1],c2[25001][sz+1],r[200001],p[200001],tin[200001],tout[200001],t,C[25001],pos[25001];
vector <int> ke[200001],ve[25001],V;
void dfs(int u){
    tin[u]=++t;
    ve[r[u]].push_back(t);
    if (C[r[u]]>sz)
        cnt[u][pos[r[u]]]++;
    for (int v:ke[u]){
        for (int i=1;i<=sz;i++)
            cnt[v][i]+=cnt[u][i];
        dfs(v);
    }
    for (int i=1;i<=sz;i++)
        c[r[u]][i]+=cnt[u][i];
    tout[u]=++t;
    ve[r[u]].push_back(-t);
}
void dfs2(int u){
    if (C[r[u]]>sz)
        cnt[u][pos[r[u]]]++;
    for (int v:ke[u]){
        dfs2(v);
        for (int i=1;i<=sz;i++)
            cnt[u][i]+=cnt[v][i];
    }
    for (int i=1;i<=sz;i++)
        c2[r[u]][i]+=cnt[u][i];
}
int32_t main(){
    ios_base::sync_with_stdio(NULL);cin.tie(nullptr);
    cin >> n >> R >> q;
    for (int i=1;i<=n;i++){
        if (i>1){
            cin >> p[i];
            ke[p[i]].push_back(i);
        }
        cin >> r[i];
        C[r[i]]++;
    }
    for (int i=1;i<=R;i++)
        V.push_back(i);
    sort(V.begin(),V.end(),[](int i, int j){return C[i]>C[j];});
    for (int i=0;i<V.size();i++)
        pos[V[i]]=i+1;
    dfs(1);
    memset(cnt,0,sizeof(cnt));
    dfs2(1);
    while (q--){
        cin >> r1 >> r2;
        if (C[r1]>sz){
            cout << c[r2][pos[r1]] << endl;
            continue;
        }
        if (C[r2]>sz){
            cout << c2[r1][pos[r2]] << endl;
            continue;
        }
        int j=0,cnt=0,res=0;
        for (int i=0;i<ve[r2].size();i++){
            while (j<ve[r1].size()){
                if (abs(ve[r1][j])>abs(ve[r2][i]))
                    break;
                cnt+=(ve[r1][j]>0)-(ve[r1][j]<0);
                j++;
            }
            if (ve[r2][i]>0)
                res+=cnt;
        }
        cout << res << endl;
    }
}

Compilation message

regions.cpp: In function 'int32_t main()':
regions.cpp:47:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for (int i=0;i<V.size();i++)
      |                  ~^~~~~~~~~
regions.cpp:63:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         for (int i=0;i<ve[r2].size();i++){
      |                      ~^~~~~~~~~~~~~~
regions.cpp:64:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |             while (j<ve[r1].size()){
      |                    ~^~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 22 ms 131072 KB Execution killed with signal 9
2 Runtime error 32 ms 131072 KB Execution killed with signal 9
3 Runtime error 23 ms 131072 KB Execution killed with signal 9
4 Runtime error 19 ms 131072 KB Execution killed with signal 9
5 Runtime error 20 ms 131072 KB Execution killed with signal 9
6 Runtime error 20 ms 131072 KB Execution killed with signal 9
7 Runtime error 21 ms 131072 KB Execution killed with signal 9
8 Runtime error 21 ms 131072 KB Execution killed with signal 9
9 Runtime error 21 ms 131072 KB Execution killed with signal 9
10 Runtime error 25 ms 131072 KB Execution killed with signal 9
11 Runtime error 30 ms 131072 KB Execution killed with signal 9
12 Runtime error 31 ms 131072 KB Execution killed with signal 9
13 Runtime error 39 ms 131072 KB Execution killed with signal 9
14 Runtime error 38 ms 131072 KB Execution killed with signal 9
15 Runtime error 44 ms 131072 KB Execution killed with signal 9

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 69 ms 131072 KB Execution killed with signal 9
2 Runtime error 68 ms 131072 KB Execution killed with signal 9
3 Runtime error 36 ms 131072 KB Execution killed with signal 9
4 Runtime error 41 ms 131072 KB Execution killed with signal 9
5 Runtime error 45 ms 131072 KB Execution killed with signal 9
6 Runtime error 56 ms 131072 KB Execution killed with signal 9
7 Runtime error 84 ms 131072 KB Execution killed with signal 9
8 Runtime error 52 ms 131072 KB Execution killed with signal 9
9 Runtime error 47 ms 131072 KB Execution killed with signal 9
10 Runtime error 49 ms 131072 KB Execution killed with signal 9
11 Runtime error 66 ms 131072 KB Execution killed with signal 9
12 Runtime error 72 ms 131072 KB Execution killed with signal 9
13 Runtime error 55 ms 131072 KB Execution killed with signal 9
14 Runtime error 86 ms 131072 KB Execution killed with signal 9
15 Runtime error 59 ms 131072 KB Execution killed with signal 9
16 Runtime error 62 ms 131072 KB Execution killed with signal 9
17 Runtime error 72 ms 131072 KB Execution killed with signal 9