oj.uz

Submission #899902

# Submission time Handle Problem Language Result Execution time Memory
899902 2024-01-07T09:15:18 Z boyliguanhan Regions (IOI09_regions) C++17
90 / 100
 8000 ms 80924 KB 
#include<bits/stdc++.h>
#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[51][25001], ans2[25001][51], in[200001], out[200001], li[200001], sz[25001], lg[51];
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]>4000)
            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:41: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]
   41 |     while(a<arr[r1].size()&&b<arr[r2].size()){
      |           ~^~~~~~~~~~~~~~~
regions.cpp:41: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]
   41 |     while(a<arr[r1].size()&&b<arr[r2].size()){
      |                             ~^~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12372 KB Output is correct
2 Correct 3 ms 12376 KB Output is correct
3 Correct 4 ms 12376 KB Output is correct
4 Correct 4 ms 12376 KB Output is correct
5 Correct 5 ms 12632 KB Output is correct
6 Correct 9 ms 12632 KB Output is correct
7 Correct 15 ms 12632 KB Output is correct
8 Correct 18 ms 12632 KB Output is correct
9 Correct 31 ms 14168 KB Output is correct
10 Correct 46 ms 13144 KB Output is correct
11 Correct 77 ms 13664 KB Output is correct
12 Correct 78 ms 14680 KB Output is correct
13 Correct 97 ms 13768 KB Output is correct
14 Correct 127 ms 14580 KB Output is correct
15 Correct 171 ms 25716 KB Output is correct

Subtask #2
75.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 619 ms 22776 KB Output is correct
2 Correct 732 ms 18556 KB Output is correct
3 Correct 1212 ms 28016 KB Output is correct
4 Correct 169 ms 14672 KB Output is correct
5 Correct 209 ms 21372 KB Output is correct
6 Correct 499 ms 17152 KB Output is correct
7 Correct 723 ms 19788 KB Output is correct
8 Correct 745 ms 39308 KB Output is correct
9 Correct 1149 ms 29580 KB Output is correct
10 Correct 1741 ms 52444 KB Output is correct
11 Correct 1788 ms 28072 KB Output is correct
12 Correct 809 ms 29360 KB Output is correct
13 Correct 1390 ms 32000 KB Output is correct
14 Correct 1445 ms 30456 KB Output is correct
15 Correct 6638 ms 47636 KB Output is correct
16 Execution timed out 8005 ms 80924 KB Time limit exceeded
17 Execution timed out 8090 ms 73268 KB Time limit exceeded