oj.uz

Submission #687069

# Submission time Handle Problem Language Result Execution time Memory
687069 2023-01-26T05:51:23 Z boyliguanhan Regions (IOI09_regions) C++17
85 / 100
 8000 ms 104588 KB 
#include<bits/stdc++.h>
#pragma GCC optimize(3)
#define l long long
using namespace std;
vector<l> adj[200001], lg;
vector<pair<l,l>> arr[25001];
l region[200001], t, ans1[201][25001], ans2[25001][201], in[200001], out[200001], li[200001], sz[25001];
void merge(map<l, l> &a, map<l, l> b){
    if(a.size()<b.size())
        swap(a, b);
    for(auto i: b)
        a[i.first]+=i.second;
}
map<l,l> dfs(l n){
    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(){
    iostream::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    l n, r, q, lr=0;
    cin >> n >> r >> q;
    cin >> region[1];
    for(l i = 2; i <= n; i++){
        l p;
        cin >> p >> region[i];
        sz[region[i]]++;
        adj[p].push_back(i);
    }
    for(int i = 1; i <= r; i++)
        if(sz[i]>1000)
            lg.push_back(i), li[i]=++lr;
    dfs(1);
    while(q--){
        int r1, r2;
        cin >> r1 >> r2;
        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 'long long int query_s(int, int)':
regions.cpp:35:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     while(a<arr[r1].size()||b<arr[r2].size()){
      |           ~^~~~~~~~~~~~~~~
regions.cpp:35:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     while(a<arr[r1].size()||b<arr[r2].size()){
      |                             ~^~~~~~~~~~~~~~~
regions.cpp:36:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         if(a<arr[r1].size()&&b<arr[r2].size()){
      |            ~^~~~~~~~~~~~~~~
regions.cpp:36:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         if(a<arr[r1].size()&&b<arr[r2].size()){
      |                              ~^~~~~~~~~~~~~~~
regions.cpp:41:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         } 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 5 ms 5584 KB Output is correct
5 Correct 9 ms 5712 KB Output is correct
6 Correct 22 ms 5840 KB Output is correct
7 Correct 28 ms 5840 KB Output is correct
8 Correct 35 ms 5840 KB Output is correct
9 Correct 32 ms 7160 KB Output is correct
10 Correct 87 ms 6736 KB Output is correct
11 Correct 130 ms 7384 KB Output is correct
12 Correct 146 ms 8704 KB Output is correct
13 Correct 97 ms 8108 KB Output is correct
14 Correct 259 ms 9168 KB Output is correct
15 Correct 235 ms 17488 KB Output is correct

Subtask #2
70.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1182 ms 16292 KB Output is correct
2 Correct 1249 ms 13496 KB Output is correct
3 Correct 1849 ms 21348 KB Output is correct
4 Correct 300 ms 9512 KB Output is correct
5 Correct 377 ms 14508 KB Output is correct
6 Correct 739 ms 12392 KB Output is correct
7 Correct 1263 ms 14152 KB Output is correct
8 Correct 1053 ms 30408 KB Output is correct
9 Correct 1850 ms 27004 KB Output is correct
10 Correct 3467 ms 42524 KB Output is correct
11 Correct 2977 ms 26672 KB Output is correct
12 Correct 1241 ms 51988 KB Output is correct
13 Correct 2154 ms 53760 KB Output is correct
14 Correct 2702 ms 62192 KB Output is correct
15 Execution timed out 8044 ms 80860 KB Time limit exceeded
16 Execution timed out 8068 ms 104588 KB Time limit exceeded
17 Execution timed out 8048 ms 93252 KB Time limit exceeded