oj.uz

Submission #703091

# Submission time Handle Problem Language Result Execution time Memory
703091 2023-02-26T04:14:50 Z boyliguanhan Regions (IOI09_regions) C++17
90 / 100
 8000 ms 74416 KB 
#include<bits/stdc++.h>
#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(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 8 ms 5584 KB Output is correct
5 Correct 11 ms 5584 KB Output is correct
6 Correct 22 ms 5840 KB Output is correct
7 Correct 18 ms 5712 KB Output is correct
8 Correct 39 ms 5840 KB Output is correct
9 Correct 44 ms 7352 KB Output is correct
10 Correct 92 ms 6352 KB Output is correct
11 Correct 103 ms 6860 KB Output is correct
12 Correct 134 ms 8032 KB Output is correct
13 Correct 150 ms 7188 KB Output is correct
14 Correct 206 ms 7860 KB Output is correct
15 Correct 219 ms 19036 KB Output is correct

Subtask #2
75.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1628 ms 14512 KB Output is correct
2 Correct 2452 ms 10540 KB Output is correct
3 Correct 1685 ms 19948 KB Output is correct
4 Correct 209 ms 8552 KB Output is correct
5 Correct 307 ms 15176 KB Output is correct
6 Correct 798 ms 11348 KB Output is correct
7 Correct 905 ms 12396 KB Output is correct
8 Correct 924 ms 32212 KB Output is correct
9 Correct 1478 ms 23248 KB Output is correct
10 Correct 2309 ms 45516 KB Output is correct
11 Correct 2043 ms 21068 KB Output is correct
12 Correct 1084 ms 21700 KB Output is correct
13 Correct 1461 ms 24588 KB Output is correct
14 Correct 1750 ms 23656 KB Output is correct
15 Correct 6797 ms 41272 KB Output is correct
16 Execution timed out 8007 ms 74416 KB Time limit exceeded
17 Execution timed out 8052 ms 66260 KB Time limit exceeded