oj.uz

Submission #852555

# Submission time Handle Problem Language Result Execution time Memory
852555 2023-09-22T05:10:00 Z abcvuitunggio Regions (IOI09_regions) C++17
1 / 100
 4433 ms 131072 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int sz=55;
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 (pos[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 (pos[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(r[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 (pos[r1]<=sz){
            cout << c[r2][pos[r1]] << endl;
            continue;
        }
        if (pos[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
1.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 103256 KB Output is correct
2 Incorrect 13 ms 103256 KB Output isn't correct
3 Incorrect 13 ms 103512 KB Output isn't correct
4 Incorrect 14 ms 103480 KB Output isn't correct
5 Incorrect 15 ms 103500 KB Output isn't correct
6 Incorrect 21 ms 102600 KB Output isn't correct
7 Incorrect 27 ms 102744 KB Output isn't correct
8 Incorrect 28 ms 102676 KB Output isn't correct
9 Incorrect 40 ms 103256 KB Output isn't correct
10 Incorrect 58 ms 104024 KB Output isn't correct
11 Incorrect 63 ms 103552 KB Output isn't correct
12 Incorrect 87 ms 105152 KB Output isn't correct
13 Incorrect 109 ms 103836 KB Output isn't correct
14 Incorrect 108 ms 104424 KB Output isn't correct
15 Incorrect 134 ms 108208 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 2340 ms 107656 KB Output isn't correct
2 Incorrect 4174 ms 106312 KB Output isn't correct
3 Incorrect 4433 ms 110856 KB Output isn't correct
4 Incorrect 145 ms 106468 KB Output isn't correct
5 Incorrect 242 ms 111080 KB Output isn't correct
6 Incorrect 516 ms 111724 KB Output isn't correct
7 Incorrect 707 ms 115028 KB Output isn't correct
8 Incorrect 698 ms 121444 KB Output isn't correct
9 Incorrect 1071 ms 125316 KB Output isn't correct
10 Runtime error 95 ms 131072 KB Execution killed with signal 9
11 Runtime error 123 ms 131072 KB Execution killed with signal 9
12 Incorrect 1120 ms 127324 KB Output isn't correct
13 Incorrect 1290 ms 127896 KB Output isn't correct
14 Incorrect 1851 ms 129620 KB Output isn't correct
15 Runtime error 128 ms 131072 KB Execution killed with signal 9
16 Runtime error 74 ms 131072 KB Execution killed with signal 9
17 Runtime error 71 ms 131072 KB Execution killed with signal 9