oj.uz

Submission #852576

# Submission time Handle Problem Language Result Execution time Memory
852576 2023-09-22T06:10:36 Z abcvuitunggio Regions (IOI09_regions) C++17
100 / 100
 1705 ms 119692 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int sz=1000;
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 2 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 10 ms 10840 KB Output is correct
7 Correct 13 ms 10840 KB Output is correct
8 Correct 15 ms 10840 KB Output is correct
9 Correct 27 ms 11352 KB Output is correct
10 Correct 42 ms 13400 KB Output is correct
11 Correct 59 ms 13812 KB Output is correct
12 Correct 74 ms 14432 KB Output is correct
13 Correct 88 ms 14116 KB Output is correct
14 Correct 126 ms 14700 KB Output is correct
15 Correct 170 ms 18624 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 600 ms 24112 KB Output is correct
2 Correct 622 ms 22752 KB Output is correct
3 Correct 1099 ms 26444 KB Output is correct
4 Correct 158 ms 14700 KB Output is correct
5 Correct 205 ms 16984 KB Output is correct
6 Correct 511 ms 15844 KB Output is correct
7 Correct 637 ms 16956 KB Output is correct
8 Correct 608 ms 23536 KB Output is correct
9 Correct 1043 ms 23056 KB Output is correct
10 Correct 1689 ms 29524 KB Output is correct
11 Correct 1705 ms 22508 KB Output is correct
12 Correct 656 ms 78696 KB Output is correct
13 Correct 870 ms 79316 KB Output is correct
14 Correct 1074 ms 91060 KB Output is correct
15 Correct 1464 ms 110908 KB Output is correct
16 Correct 1643 ms 119692 KB Output is correct
17 Correct 1489 ms 104740 KB Output is correct