oj.uz

Submission #852553

# Submission time Handle Problem Language Result Execution time Memory
852553 2023-09-22T05:04:47 Z abcvuitunggio Regions (IOI09_regions) C++17
1 / 100
 6473 ms 131072 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int sz=58;
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];
    tout[u]=++t;
    ve[r[u]].push_back(-t);
}
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:49: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]
   49 |     for (int i=0;i<V.size();i++)
      |                  ~^~~~~~~~~
regions.cpp:65: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]
   65 |         for (int i=0;i<ve[r2].size();i++){
      |                      ~^~~~~~~~~~~~~~
regions.cpp:66: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]
   66 |             while (j<ve[r1].size()){
      |                    ~^~~~~~~~~~~~~~

Subtask #1
1.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 109144 KB Output is correct
2 Incorrect 12 ms 109144 KB Output isn't correct
3 Incorrect 15 ms 109144 KB Output isn't correct
4 Incorrect 15 ms 109144 KB Output isn't correct
5 Incorrect 16 ms 109400 KB Output isn't correct
6 Incorrect 19 ms 107352 KB Output isn't correct
7 Incorrect 22 ms 107428 KB Output isn't correct
8 Incorrect 28 ms 107352 KB Output isn't correct
9 Incorrect 34 ms 108120 KB Output isn't correct
10 Incorrect 56 ms 110088 KB Output isn't correct
11 Incorrect 78 ms 108524 KB Output isn't correct
12 Incorrect 79 ms 111264 KB Output isn't correct
13 Incorrect 99 ms 108652 KB Output isn't correct
14 Incorrect 106 ms 109404 KB Output isn't correct
15 Incorrect 131 ms 113964 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 3370 ms 113732 KB Output isn't correct
2 Incorrect 6227 ms 111856 KB Output isn't correct
3 Incorrect 6473 ms 118776 KB Output isn't correct
4 Incorrect 159 ms 113488 KB Output isn't correct
5 Incorrect 234 ms 116692 KB Output isn't correct
6 Incorrect 655 ms 117240 KB Output isn't correct
7 Incorrect 885 ms 120672 KB Output isn't correct
8 Incorrect 742 ms 128744 KB Output isn't correct
9 Incorrect 1191 ms 130944 KB Output isn't correct
10 Runtime error 94 ms 131072 KB Execution killed with signal 9
11 Runtime error 131 ms 131072 KB Execution killed with signal 9
12 Runtime error 171 ms 131072 KB Execution killed with signal 9
13 Runtime error 111 ms 131072 KB Execution killed with signal 9
14 Runtime error 133 ms 131072 KB Execution killed with signal 9
15 Runtime error 67 ms 131072 KB Execution killed with signal 9
16 Runtime error 70 ms 131072 KB Execution killed with signal 9
17 Runtime error 76 ms 131072 KB Execution killed with signal 9