oj.uz

Submission #687063

# Submission time Handle Problem Language Result Execution time Memory
687063 2023-01-26T05:47:52 Z boyliguanhan Regions (IOI09_regions) C++17
85 / 100
 8000 ms 107344 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[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, 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 5 ms 5584 KB Output is correct
4 Correct 7 ms 5584 KB Output is correct
5 Correct 6 ms 5584 KB Output is correct
6 Correct 23 ms 5840 KB Output is correct
7 Correct 31 ms 5728 KB Output is correct
8 Correct 40 ms 5840 KB Output is correct
9 Correct 70 ms 7120 KB Output is correct
10 Correct 94 ms 6676 KB Output is correct
11 Correct 160 ms 7332 KB Output is correct
12 Correct 149 ms 8732 KB Output is correct
13 Correct 192 ms 8076 KB Output is correct
14 Correct 204 ms 9152 KB Output is correct
15 Correct 356 ms 18188 KB Output is correct

Subtask #2
70.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1168 ms 16468 KB Output is correct
2 Correct 1170 ms 13496 KB Output is correct
3 Correct 2377 ms 21884 KB Output is correct
4 Correct 307 ms 9456 KB Output is correct
5 Correct 457 ms 14876 KB Output is correct
6 Correct 899 ms 12316 KB Output is correct
7 Correct 1447 ms 14152 KB Output is correct
8 Correct 1134 ms 31504 KB Output is correct
9 Correct 1857 ms 27288 KB Output is correct
10 Correct 3033 ms 43900 KB Output is correct
11 Correct 3223 ms 26928 KB Output is correct
12 Correct 1351 ms 51992 KB Output is correct
13 Correct 2369 ms 53992 KB Output is correct
14 Correct 2891 ms 62088 KB Output is correct
15 Execution timed out 8055 ms 81864 KB Time limit exceeded
16 Execution timed out 8050 ms 107344 KB Time limit exceeded
17 Execution timed out 8093 ms 95920 KB Time limit exceeded