oj.uz

Submission #899678

# Submission time Handle Problem Language Result Execution time Memory
899678 2024-01-06T20:51:14 Z boyliguanhan Regions (IOI09_regions) C++17
80 / 100
 8000 ms 78984 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;
}
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])
            cout << ans1[li[r1]][r2] << endl;
        else if(li[r2])
            cout << ans2[r1][li[r2]] << endl;
        else
            cout << query_s(r1, r2) << endl;
    }
    return 0;
}

Compilation message

regions.cpp: In function 'int query_s(int, int)':
regions.cpp:45: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]
   45 |     while(a<arr[r1].size()||b<arr[r2].size()){
      |           ~^~~~~~~~~~~~~~~
regions.cpp:45: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]
   45 |     while(a<arr[r1].size()||b<arr[r2].size()){
      |                             ~^~~~~~~~~~~~~~~
regions.cpp:46: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]
   46 |         if(a<arr[r1].size()&&b<arr[r2].size()){
      |            ~^~~~~~~~~~~~~~~
regions.cpp:46: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]
   46 |         if(a<arr[r1].size()&&b<arr[r2].size()){
      |                              ~^~~~~~~~~~~~~~~
regions.cpp:51: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]
   51 |         } 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 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 11 ms 11096 KB Output is correct
7 Correct 16 ms 10840 KB Output is correct
8 Correct 21 ms 10840 KB Output is correct
9 Correct 45 ms 12376 KB Output is correct
10 Correct 48 ms 11860 KB Output is correct
11 Correct 90 ms 11940 KB Output is correct
12 Correct 151 ms 13144 KB Output is correct
13 Correct 112 ms 12068 KB Output is correct
14 Correct 173 ms 12780 KB Output is correct
15 Correct 300 ms 24580 KB Output is correct

Subtask #2
65.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2556 ms 21188 KB Output is correct
2 Correct 3949 ms 18356 KB Output is correct
3 Correct 2344 ms 27272 KB Output is correct
4 Correct 301 ms 13184 KB Output is correct
5 Correct 1223 ms 20164 KB Output is correct
6 Correct 1077 ms 15636 KB Output is correct
7 Correct 1556 ms 16924 KB Output is correct
8 Correct 7193 ms 37148 KB Output is correct
9 Correct 4988 ms 26708 KB Output is correct
10 Execution timed out 8019 ms 49716 KB Time limit exceeded
11 Correct 3353 ms 25600 KB Output is correct
12 Correct 1639 ms 25572 KB Output is correct
13 Correct 5218 ms 29312 KB Output is correct
14 Correct 3038 ms 28772 KB Output is correct
15 Execution timed out 8026 ms 42672 KB Time limit exceeded
16 Execution timed out 8058 ms 78984 KB Time limit exceeded
17 Execution timed out 8025 ms 71920 KB Time limit exceeded