oj.uz

Submission #852575

# Submission time Handle Problem Language Result Execution time Memory
852575 2023-09-22T06:09:59 Z abcvuitunggio Regions (IOI09_regions) C++17
80 / 100
 1684 ms 131072 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int sz=500;
int lim,n,R,q,r1,r2,cnt[25001],c[25001][200000/sz+1],c2[25001][200000/sz+1],sum[400001],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);
    for (int i=1;i<=lim;i++)
        c[r[u]][i]+=cnt[i];
    if (C[r[u]]>sz)
        cnt[pos[r[u]]]++;
    for (int v:ke[u])
        dfs(v);
    tout[u]=++t;
    ve[r[u]].push_back(-t);
    if (C[r[u]]>sz)
        cnt[pos[r[u]]]--;
}
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;
        if (C[V[i]]>sz)
            lim=i+1;
    }
    dfs(1);
    for (int i=1;i<=R;i++)
        if (C[i]>sz){
            memset(sum,0,sizeof(sum));
            for (int j:ve[i])
                if (j>0)
                    sum[j]++;
            for (int j=1;j<=n*2;j++)
                sum[j]+=sum[j-1];
            for (int j=1;j<=n;j++)
                c2[r[j]][pos[i]]+=sum[tout[j]]-sum[tin[j]-1];
        }
    while (q--){
        cin >> r1 >> r2;
        if (ve[r1].empty()||ve[r2].empty()){
            cout << 0 << endl;
            continue;
        }
        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:ve[r2]){
            while (j<ve[r1].size()){
                if (abs(ve[r1][j])>abs(i))
                    break;
                cnt+=(ve[r1][j]>0)-(ve[r1][j]<0);
                j++;
            }
            if (i>0)
                res+=cnt;
        }
        cout << res << endl;
    }
}

Compilation message

regions.cpp: In function 'int32_t main()':
regions.cpp:35: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]
   35 |     for (int i=0;i<V.size();i++){
      |                  ~^~~~~~~~~
regions.cpp:68: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]
   68 |             while (j<ve[r1].size()){
      |                    ~^~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 2 ms 10840 KB Output is correct
3 Correct 3 ms 10840 KB Output is correct
4 Correct 4 ms 10840 KB Output is correct
5 Correct 5 ms 10840 KB Output is correct
6 Correct 9 ms 10840 KB Output is correct
7 Correct 12 ms 10840 KB Output is correct
8 Correct 17 ms 10884 KB Output is correct
9 Correct 26 ms 11608 KB Output is correct
10 Correct 39 ms 13400 KB Output is correct
11 Correct 73 ms 13912 KB Output is correct
12 Correct 80 ms 14432 KB Output is correct
13 Correct 94 ms 14112 KB Output is correct
14 Correct 108 ms 14704 KB Output is correct
15 Correct 161 ms 18420 KB Output is correct

Subtask #2
65.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 566 ms 24108 KB Output is correct
2 Correct 577 ms 22752 KB Output is correct
3 Correct 1175 ms 26444 KB Output is correct
4 Correct 147 ms 14692 KB Output is correct
5 Correct 210 ms 16972 KB Output is correct
6 Correct 517 ms 15704 KB Output is correct
7 Correct 654 ms 16960 KB Output is correct
8 Correct 661 ms 23544 KB Output is correct
9 Correct 1052 ms 23048 KB Output is correct
10 Correct 1666 ms 29020 KB Output is correct
11 Correct 1684 ms 22232 KB Output is correct
12 Correct 628 ms 127804 KB Output is correct
13 Correct 914 ms 128552 KB Output is correct
14 Runtime error 95 ms 131072 KB Execution killed with signal 9
15 Runtime error 69 ms 131072 KB Execution killed with signal 9
16 Runtime error 72 ms 131072 KB Execution killed with signal 9
17 Runtime error 74 ms 131072 KB Execution killed with signal 9