oj.uz

Submission #899695

# Submission time Handle Problem Language Result Execution time Memory
899695 2024-01-06T21:51:03 Z boyliguanhan Regions (IOI09_regions) C++17
80 / 100
 8000 ms 78980 KB 
#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace __gnu_pbds;
#pragma GCC optimize(2)
#define l int
int read(){
    char x = getchar();
    int val = 0;
    while(x<'0'||x>'9')x=getchar();
    while('0'<=x&&x<='9')
        val = val*10+x-'0', x=getchar();
    return val;
}
void print(int num){
    if(num<0){
        putchar('-');
        num*=-1;
    }
    if(num>9) {
        print(num/10);
    }
    putchar((num%10)^48);
}
using namespace std;
vector<l> adj[200001];
vector<pair<l,l>> arr[25001];
l region[200001], t, ans1[21][25001], ans2[25001][21], in[200001], out[200001], li[200001], sz[25001], lg[21];
void merge(gp_hash_table<l, l> &a, gp_hash_table<l, l> b){
    if(a.size()<b.size())
        swap(a, b);
    for(auto i: b)
        a[i.first]+=i.second;
}
gp_hash_table<l,l> dfs(l n){
    gp_hash_table<l,l> cur;
    cur[region[n]]=1;
    in[n]=t++;
    arr[region[n]].push_back({in[n],1});
    for(auto i: adj[n]){
        merge(cur, dfs(i));
    }
    out[n]=t++;
    arr[region[n]].push_back({out[n],0});
    if(li[region[n]])
        for(auto i: cur)
            ans1[li[region[n]]][i.first]+=i.second;
    else
        for(auto i: lg)
            ans2[region[n]][li[i]]+=cur[i];
    return cur;
}
l query_s(int r1, int r2){
    l sum=0, o=0, a=0, b=0;
    vector<int> v;
    while(a<arr[r1].size()||b<arr[r2].size()){
        if(a<arr[r1].size()&&b<arr[r2].size()){
            if(arr[r1][a]<arr[r2][b])
                v.push_back(arr[r1][a].second*2-1), a++;
            else
                v.push_back(0), b++;
        } else if(a<arr[r1].size())
            v.push_back(arr[r1][a].second*2-1), a++;
        else
            v.push_back(0), b++;
    }
    for(auto i: v)
        if(i)
            o+=i;
        else
            sum+=o;
    return sum/2;
}
int main(){
    l n=read(), r=read(), q=read(), lr=0;
    region[1]=read();
    for(l i = 2; i <= n; i++){
        adj[read()].push_back(i);
        region[i] = read();
        sz[region[i]]++;
    }
    for(int i = 1; i <= r; i++)
        if(sz[i]>10000)
            lg[lr]=i, li[i]=++lr;
    dfs(1);
    while(q--){
        int r1=read(), r2=read();
        if(li[r1])
            print(ans1[li[r1]][r2]),cout<<endl;
        else if(li[r2])
            print(ans2[r1][li[r2]]),cout<<endl;
        else
            print(query_s(r1, r2)),cout<<endl;
    }
    return 0;
}

Compilation message

regions.cpp: In function 'int query_s(int, int)':
regions.cpp:55:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     while(a<arr[r1].size()||b<arr[r2].size()){
      |           ~^~~~~~~~~~~~~~~
regions.cpp:55:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     while(a<arr[r1].size()||b<arr[r2].size()){
      |                             ~^~~~~~~~~~~~~~~
regions.cpp:56:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         if(a<arr[r1].size()&&b<arr[r2].size()){
      |            ~^~~~~~~~~~~~~~~
regions.cpp:56:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         if(a<arr[r1].size()&&b<arr[r2].size()){
      |                              ~^~~~~~~~~~~~~~~
regions.cpp:61:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |         } else if(a<arr[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 6 ms 10840 KB Output is correct
6 Correct 13 ms 11096 KB Output is correct
7 Correct 16 ms 10840 KB Output is correct
8 Correct 18 ms 10840 KB Output is correct
9 Correct 46 ms 12376 KB Output is correct
10 Correct 54 ms 11352 KB Output is correct
11 Correct 91 ms 11928 KB Output is correct
12 Correct 154 ms 13108 KB Output is correct
13 Correct 124 ms 12060 KB Output is correct
14 Correct 170 ms 12992 KB Output is correct
15 Correct 301 ms 24756 KB Output is correct

Subtask #2
65.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2623 ms 21180 KB Output is correct
2 Correct 3969 ms 18216 KB Output is correct
3 Correct 2400 ms 26752 KB Output is correct
4 Correct 246 ms 13304 KB Output is correct
5 Correct 1250 ms 20324 KB Output is correct
6 Correct 1081 ms 15556 KB Output is correct
7 Correct 1600 ms 16752 KB Output is correct
8 Correct 7217 ms 37464 KB Output is correct
9 Correct 5020 ms 26464 KB Output is correct
10 Execution timed out 8016 ms 49784 KB Time limit exceeded
11 Correct 3372 ms 25536 KB Output is correct
12 Correct 1575 ms 25764 KB Output is correct
13 Correct 5260 ms 29328 KB Output is correct
14 Correct 3084 ms 29268 KB Output is correct
15 Execution timed out 8037 ms 42696 KB Time limit exceeded
16 Execution timed out 8095 ms 78980 KB Time limit exceeded
17 Execution timed out 8099 ms 72228 KB Time limit exceeded