oj.uz

Submission #687207

# Submission time Handle Problem Language Result Execution time Memory
687207 2023-01-26T07:40:09 Z boyliguanhan Regions (IOI09_regions) C++17
90 / 100
 8000 ms 74260 KB 
#include<bits/stdc++.h>
#pragma GCC optimize(3)
#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(unordered_map<l, l> &a, unordered_map<l, l> b){
    if(a.size()<b.size())
        swap(a, b);
    for(auto i: b)
        a[i.first]+=i.second;
}
unordered_map<l,l> dfs(l n){
    unordered_map<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],-1});
    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;
    while(a<arr[r1].size()&&b<arr[r2].size()){
        if(arr[r1][a]<arr[r2][b])
            o+=arr[r1][a].second, a++;
        else
            sum+=o, b++;
    }
    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:42: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]
   42 |     while(a<arr[r1].size()&&b<arr[r2].size()){
      |           ~^~~~~~~~~~~~~~~
regions.cpp:42: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]
   42 |     while(a<arr[r1].size()&&b<arr[r2].size()){
      |                             ~^~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5584 KB Output is correct
2 Correct 4 ms 5584 KB Output is correct
3 Correct 6 ms 5584 KB Output is correct
4 Correct 7 ms 5584 KB Output is correct
5 Correct 10 ms 5584 KB Output is correct
6 Correct 21 ms 5840 KB Output is correct
7 Correct 32 ms 5712 KB Output is correct
8 Correct 37 ms 5840 KB Output is correct
9 Correct 46 ms 7248 KB Output is correct
10 Correct 80 ms 6352 KB Output is correct
11 Correct 103 ms 6864 KB Output is correct
12 Correct 83 ms 8024 KB Output is correct
13 Correct 160 ms 7076 KB Output is correct
14 Correct 166 ms 7892 KB Output is correct
15 Correct 227 ms 18988 KB Output is correct

Subtask #2
75.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1806 ms 14520 KB Output is correct
2 Correct 2351 ms 10548 KB Output is correct
3 Correct 1852 ms 19980 KB Output is correct
4 Correct 229 ms 8444 KB Output is correct
5 Correct 192 ms 15248 KB Output is correct
6 Correct 732 ms 11352 KB Output is correct
7 Correct 1055 ms 12400 KB Output is correct
8 Correct 834 ms 32208 KB Output is correct
9 Correct 1498 ms 23204 KB Output is correct
10 Correct 2001 ms 45528 KB Output is correct
11 Correct 2400 ms 21136 KB Output is correct
12 Correct 1268 ms 21692 KB Output is correct
13 Correct 1919 ms 24580 KB Output is correct
14 Correct 2023 ms 23680 KB Output is correct
15 Correct 7255 ms 41200 KB Output is correct
16 Execution timed out 8018 ms 74260 KB Time limit exceeded
17 Execution timed out 8039 ms 66104 KB Time limit exceeded