oj.uz

Submission #687058

# Submission time Handle Problem Language Result Execution time Memory
687058 2023-01-26T05:41:20 Z boyliguanhan Regions (IOI09_regions) C++17
55 / 100
 3913 ms 108284 KB 
#include<bits/stdc++.h>
#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[n])
        for(auto i: cur)
            ans1[li[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, 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:34: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]
   34 |     while(a<arr[r1].size()||b<arr[r2].size()){
      |           ~^~~~~~~~~~~~~~~
regions.cpp:34: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]
   34 |     while(a<arr[r1].size()||b<arr[r2].size()){
      |                             ~^~~~~~~~~~~~~~~
regions.cpp:35: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]
   35 |         if(a<arr[r1].size()&&b<arr[r2].size()){
      |            ~^~~~~~~~~~~~~~~
regions.cpp:35: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]
   35 |         if(a<arr[r1].size()&&b<arr[r2].size()){
      |                              ~^~~~~~~~~~~~~~~
regions.cpp:40: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]
   40 |         } 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 4 ms 5584 KB Output is correct
4 Correct 8 ms 5584 KB Output is correct
5 Correct 10 ms 5584 KB Output is correct
6 Correct 20 ms 5840 KB Output is correct
7 Correct 26 ms 5712 KB Output is correct
8 Correct 45 ms 5840 KB Output is correct
9 Correct 56 ms 7140 KB Output is correct
10 Correct 81 ms 6736 KB Output is correct
11 Correct 122 ms 7396 KB Output is correct
12 Correct 168 ms 8728 KB Output is correct
13 Correct 184 ms 8076 KB Output is correct
14 Correct 258 ms 9160 KB Output is correct
15 Correct 410 ms 18136 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1120 ms 16496 KB Output isn't correct
2 Incorrect 1297 ms 13668 KB Output isn't correct
3 Incorrect 2247 ms 21796 KB Output isn't correct
4 Correct 285 ms 9392 KB Output is correct
5 Correct 420 ms 14884 KB Output is correct
6 Correct 1061 ms 12316 KB Output is correct
7 Correct 1236 ms 14156 KB Output is correct
8 Correct 1419 ms 31444 KB Output is correct
9 Correct 2318 ms 27284 KB Output is correct
10 Correct 3913 ms 43912 KB Output is correct
11 Correct 3307 ms 26900 KB Output is correct
12 Incorrect 1381 ms 51744 KB Output isn't correct
13 Incorrect 2003 ms 53872 KB Output isn't correct
14 Incorrect 2139 ms 61648 KB Output isn't correct
15 Incorrect 2847 ms 81548 KB Output isn't correct
16 Incorrect 3306 ms 108284 KB Output isn't correct
17 Incorrect 2950 ms 97780 KB Output isn't correct