oj.uz

Submission #703092

# Submission time Handle Problem Language Result Execution time Memory
703092 2023-02-26T04:17:41 Z boyliguanhan Regions (IOI09_regions) C++17
90 / 100
 8000 ms 74308 KB 
#include<bits/stdc++.h>
#pragma GCC optimize(3)
#define l int
int read(){
    char x = getchar_unlocked();
    int val = 0;
    while(x<'0'||x>'9')x=getchar_unlocked();
    while('0'<=x&&x<='9')
        val = val*10+x-'0', x=getchar_unlocked();
    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 3 ms 5584 KB Output is correct
3 Correct 4 ms 5584 KB Output is correct
4 Correct 7 ms 5584 KB Output is correct
5 Correct 9 ms 5584 KB Output is correct
6 Correct 15 ms 5840 KB Output is correct
7 Correct 27 ms 5712 KB Output is correct
8 Correct 23 ms 5840 KB Output is correct
9 Correct 42 ms 7376 KB Output is correct
10 Correct 72 ms 6372 KB Output is correct
11 Correct 90 ms 6860 KB Output is correct
12 Correct 121 ms 8016 KB Output is correct
13 Correct 158 ms 7072 KB Output is correct
14 Correct 180 ms 7900 KB Output is correct
15 Correct 226 ms 19024 KB Output is correct

Subtask #2
75.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1370 ms 14632 KB Output is correct
2 Correct 2297 ms 10548 KB Output is correct
3 Correct 2015 ms 20040 KB Output is correct
4 Correct 248 ms 8520 KB Output is correct
5 Correct 274 ms 15244 KB Output is correct
6 Correct 754 ms 11472 KB Output is correct
7 Correct 955 ms 12396 KB Output is correct
8 Correct 774 ms 32340 KB Output is correct
9 Correct 1157 ms 23368 KB Output is correct
10 Correct 1844 ms 45512 KB Output is correct
11 Correct 2290 ms 21080 KB Output is correct
12 Correct 1067 ms 21720 KB Output is correct
13 Correct 1923 ms 24584 KB Output is correct
14 Correct 1786 ms 23564 KB Output is correct
15 Correct 7023 ms 41264 KB Output is correct
16 Execution timed out 8077 ms 74308 KB Time limit exceeded
17 Execution timed out 8013 ms 66352 KB Time limit exceeded