oj.uz

Submission #687185

# Submission time Handle Problem Language Result Execution time Memory
687185 2023-01-26T07:23:46 Z boyliguanhan Regions (IOI09_regions) C++17
90 / 100
 8000 ms 74536 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[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 4 ms 5584 KB Output is correct
3 Correct 6 ms 5584 KB Output is correct
4 Correct 10 ms 5584 KB Output is correct
5 Correct 7 ms 5584 KB Output is correct
6 Correct 17 ms 5840 KB Output is correct
7 Correct 19 ms 5744 KB Output is correct
8 Correct 34 ms 5840 KB Output is correct
9 Correct 60 ms 7376 KB Output is correct
10 Correct 86 ms 6352 KB Output is correct
11 Correct 132 ms 6860 KB Output is correct
12 Correct 125 ms 8016 KB Output is correct
13 Correct 177 ms 7092 KB Output is correct
14 Correct 251 ms 7888 KB Output is correct
15 Correct 307 ms 19040 KB Output is correct

Subtask #2
75.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 3241 ms 14596 KB Output is correct
2 Correct 4475 ms 10784 KB Output is correct
3 Correct 3610 ms 20048 KB Output is correct
4 Correct 283 ms 8548 KB Output is correct
5 Correct 426 ms 15204 KB Output is correct
6 Correct 874 ms 11364 KB Output is correct
7 Correct 1395 ms 12400 KB Output is correct
8 Correct 1242 ms 32212 KB Output is correct
9 Correct 1819 ms 23292 KB Output is correct
10 Correct 3425 ms 45472 KB Output is correct
11 Correct 3106 ms 21136 KB Output is correct
12 Correct 1141 ms 21828 KB Output is correct
13 Correct 2033 ms 24580 KB Output is correct
14 Correct 2033 ms 23628 KB Output is correct
15 Correct 7266 ms 41264 KB Output is correct
16 Execution timed out 8020 ms 74536 KB Time limit exceeded
17 Execution timed out 8010 ms 66284 KB Time limit exceeded