oj.uz

Submission #687183

# Submission time Handle Problem Language Result Execution time Memory
687183 2023-01-26T07:22:02 Z boyliguanhan Regions (IOI09_regions) C++17
90 / 100
 8000 ms 76236 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[41][25001], ans2[25001][41], in[200001], out[200001], li[200001], sz[25001], lg[41];
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]>5000)
            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 4 ms 5584 KB Output is correct
3 Correct 4 ms 5584 KB Output is correct
4 Correct 6 ms 5584 KB Output is correct
5 Correct 9 ms 5584 KB Output is correct
6 Correct 19 ms 5840 KB Output is correct
7 Correct 29 ms 5712 KB Output is correct
8 Correct 26 ms 5840 KB Output is correct
9 Correct 53 ms 7376 KB Output is correct
10 Correct 81 ms 6404 KB Output is correct
11 Correct 104 ms 6880 KB Output is correct
12 Correct 134 ms 8068 KB Output is correct
13 Correct 100 ms 7104 KB Output is correct
14 Correct 241 ms 7896 KB Output is correct
15 Correct 347 ms 19072 KB Output is correct

Subtask #2
75.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 939 ms 14536 KB Output is correct
2 Correct 1313 ms 10516 KB Output is correct
3 Correct 2118 ms 19972 KB Output is correct
4 Correct 283 ms 8804 KB Output is correct
5 Correct 353 ms 15624 KB Output is correct
6 Correct 1067 ms 11888 KB Output is correct
7 Correct 1112 ms 13184 KB Output is correct
8 Correct 1245 ms 32996 KB Output is correct
9 Correct 2116 ms 24484 KB Output is correct
10 Correct 2931 ms 47400 KB Output is correct
11 Correct 2916 ms 23092 KB Output is correct
12 Correct 1069 ms 22884 KB Output is correct
13 Correct 1904 ms 25844 KB Output is correct
14 Correct 2256 ms 25180 KB Output is correct
15 Correct 7753 ms 43096 KB Output is correct
16 Execution timed out 8087 ms 76236 KB Time limit exceeded
17 Execution timed out 8042 ms 67716 KB Time limit exceeded