oj.uz

Submission #852563

# Submission time Handle Problem Language Result Execution time Memory
852563 2023-09-22T05:40:38 Z abcvuitunggio Regions (IOI09_regions) C++17
25 / 100
 244 ms 131072 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int sz=416;
int n,R,q,r1,r2,cnt[200001][25000/sz+1],c[25001][25000/sz+1],c2[25001][25000/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<=25000/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<=25000/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()){
      |                    ~^~~~~~~~~~~~~~
regions.cpp: In function 'void dfs2(long long int)':
regions.cpp:28:22: warning: iteration 60 invokes undefined behavior [-Waggressive-loop-optimizations]
   28 |             cnt[u][i]+=cnt[v][i];
      |             ~~~~~~~~~^~~~~~~~~~~
regions.cpp:27:23: note: within this loop
   27 |         for (int i=1;i<=sz;i++)
      |                      ~^~~~
regions.cpp: In function 'void dfs(long long int)':
regions.cpp:14:22: warning: iteration 60 invokes undefined behavior [-Waggressive-loop-optimizations]
   14 |             cnt[v][i]+=cnt[u][i];
      |             ~~~~~~~~~^~~~~~~~~~~
regions.cpp:13:23: note: within this loop
   13 |         for (int i=1;i<=sz;i++)
      |                      ~^~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 110268 KB Output is correct
2 Correct 14 ms 110424 KB Output is correct
3 Correct 14 ms 110424 KB Output is correct
4 Correct 16 ms 110424 KB Output is correct
5 Correct 17 ms 110436 KB Output is correct
6 Correct 22 ms 110424 KB Output is correct
7 Correct 28 ms 110424 KB Output is correct
8 Correct 33 ms 110480 KB Output is correct
9 Correct 38 ms 110936 KB Output is correct
10 Correct 56 ms 110924 KB Output is correct
11 Correct 94 ms 111356 KB Output is correct
12 Correct 96 ms 111972 KB Output is correct
13 Correct 130 ms 111656 KB Output is correct
14 Correct 173 ms 112248 KB Output is correct
15 Correct 202 ms 115960 KB Output is correct

Subtask #2
10.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 86 ms 116224 KB Execution killed with signal 13
2 Runtime error 82 ms 115136 KB Execution killed with signal 13
3 Runtime error 96 ms 117832 KB Execution killed with signal 13
4 Correct 181 ms 116348 KB Output is correct
5 Correct 244 ms 118620 KB Output is correct
6 Runtime error 71 ms 122400 KB Execution killed with signal 13
7 Runtime error 89 ms 124764 KB Execution killed with signal 13
8 Runtime error 115 ms 130220 KB Execution killed with signal 13
9 Runtime error 137 ms 131072 KB Execution killed with signal 9
10 Runtime error 121 ms 131072 KB Execution killed with signal 9
11 Runtime error 172 ms 131072 KB Execution killed with signal 9
12 Runtime error 199 ms 131072 KB Execution killed with signal 9
13 Runtime error 148 ms 131072 KB Execution killed with signal 9
14 Runtime error 184 ms 131072 KB Execution killed with signal 9
15 Runtime error 71 ms 131072 KB Execution killed with signal 9
16 Runtime error 115 ms 131072 KB Execution killed with signal 9
17 Runtime error 91 ms 131072 KB Execution killed with signal 9