oj.uz

Submission #687079

# Submission time Handle Problem Language Result Execution time Memory
687079 2023-01-26T05:55:33 Z boyliguanhan Regions (IOI09_regions) C++17
80 / 100
 8000 ms 131072 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[450][25001], ans2[25001][450], 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]>450)
            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 4 ms 5568 KB Output is correct
3 Correct 6 ms 5584 KB Output is correct
4 Correct 7 ms 5584 KB Output is correct
5 Correct 11 ms 5712 KB Output is correct
6 Correct 20 ms 5840 KB Output is correct
7 Correct 37 ms 5840 KB Output is correct
8 Correct 33 ms 5840 KB Output is correct
9 Correct 61 ms 7148 KB Output is correct
10 Correct 85 ms 6736 KB Output is correct
11 Correct 113 ms 7384 KB Output is correct
12 Correct 161 ms 8696 KB Output is correct
13 Correct 158 ms 8108 KB Output is correct
14 Correct 171 ms 9160 KB Output is correct
15 Correct 357 ms 17488 KB Output is correct

Subtask #2
65.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1074 ms 16788 KB Output is correct
2 Correct 1066 ms 14044 KB Output is correct
3 Correct 1869 ms 21856 KB Output is correct
4 Correct 307 ms 9504 KB Output is correct
5 Correct 398 ms 14496 KB Output is correct
6 Correct 845 ms 38256 KB Output is correct
7 Correct 1184 ms 50460 KB Output is correct
8 Correct 5032 ms 73756 KB Output is correct
9 Correct 1788 ms 27000 KB Output is correct
10 Runtime error 3055 ms 131072 KB Execution killed with signal 9
11 Correct 2755 ms 26668 KB Output is correct
12 Correct 1351 ms 77400 KB Output is correct
13 Correct 2214 ms 79200 KB Output is correct
14 Correct 2728 ms 94204 KB Output is correct
15 Execution timed out 8020 ms 129080 KB Time limit exceeded
16 Runtime error 3583 ms 131072 KB Execution killed with signal 9
17 Execution timed out 8105 ms 119544 KB Time limit exceeded