oj.uz

Submission #703094

# Submission time Handle Problem Language Result Execution time Memory
703094 2023-02-26T04:21:03 Z boyliguanhan Regions (IOI09_regions) C++17
90 / 100
 8000 ms 74272 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],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:43: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]
   43 |     while(a<arr[r1].size()||b<arr[r2].size()){
      |           ~^~~~~~~~~~~~~~~
regions.cpp:43: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]
   43 |     while(a<arr[r1].size()||b<arr[r2].size()){
      |                             ~^~~~~~~~~~~~~~~
regions.cpp:44: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]
   44 |         if(a<arr[r1].size()&&b<arr[r2].size()){
      |            ~^~~~~~~~~~~~~~~
regions.cpp:44: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]
   44 |         if(a<arr[r1].size()&&b<arr[r2].size()){
      |                              ~^~~~~~~~~~~~~~~
regions.cpp:49: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]
   49 |         } else if(a<arr[r1].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 5 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 5896 KB Output is correct
7 Correct 25 ms 5712 KB Output is correct
8 Correct 37 ms 5840 KB Output is correct
9 Correct 53 ms 7344 KB Output is correct
10 Correct 83 ms 6352 KB Output is correct
11 Correct 117 ms 6892 KB Output is correct
12 Correct 127 ms 8016 KB Output is correct
13 Correct 166 ms 7084 KB Output is correct
14 Correct 222 ms 7852 KB Output is correct
15 Correct 295 ms 19012 KB Output is correct

Subtask #2
75.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 3048 ms 14660 KB Output is correct
2 Correct 4174 ms 10780 KB Output is correct
3 Correct 2417 ms 20048 KB Output is correct
4 Correct 267 ms 8460 KB Output is correct
5 Correct 361 ms 15240 KB Output is correct
6 Correct 926 ms 11348 KB Output is correct
7 Correct 978 ms 12400 KB Output is correct
8 Correct 1184 ms 32216 KB Output is correct
9 Correct 1662 ms 23236 KB Output is correct
10 Correct 3123 ms 45420 KB Output is correct
11 Correct 3117 ms 21116 KB Output is correct
12 Correct 1225 ms 21692 KB Output is correct
13 Correct 1919 ms 24588 KB Output is correct
14 Correct 2175 ms 23616 KB Output is correct
15 Correct 7249 ms 41148 KB Output is correct
16 Execution timed out 8080 ms 74272 KB Time limit exceeded
17 Execution timed out 8022 ms 66388 KB Time limit exceeded