oj.uz

Submission #687066

# Submission time Handle Problem Language Result Execution time Memory
687066 2023-01-26T05:49:44 Z boyliguanhan Regions (IOI09_regions) C++17
85 / 100
 8000 ms 104420 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(){
    cin.sync_with_stdio(false);
    cin.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 4 ms 5584 KB Output is correct
2 Correct 3 ms 5584 KB Output is correct
3 Correct 6 ms 5584 KB Output is correct
4 Correct 7 ms 5584 KB Output is correct
5 Correct 14 ms 5712 KB Output is correct
6 Correct 12 ms 5840 KB Output is correct
7 Correct 37 ms 5840 KB Output is correct
8 Correct 54 ms 5840 KB Output is correct
9 Correct 57 ms 7152 KB Output is correct
10 Correct 82 ms 6736 KB Output is correct
11 Correct 136 ms 7384 KB Output is correct
12 Correct 146 ms 8692 KB Output is correct
13 Correct 173 ms 8108 KB Output is correct
14 Correct 257 ms 9160 KB Output is correct
15 Correct 354 ms 17564 KB Output is correct

Subtask #2
70.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1065 ms 16316 KB Output is correct
2 Correct 1113 ms 13496 KB Output is correct
3 Correct 2053 ms 21308 KB Output is correct
4 Correct 324 ms 9512 KB Output is correct
5 Correct 306 ms 14512 KB Output is correct
6 Correct 971 ms 12320 KB Output is correct
7 Correct 1333 ms 14156 KB Output is correct
8 Correct 1124 ms 30412 KB Output is correct
9 Correct 1697 ms 27000 KB Output is correct
10 Correct 3342 ms 42528 KB Output is correct
11 Correct 3207 ms 26672 KB Output is correct
12 Correct 1389 ms 51976 KB Output is correct
13 Correct 2052 ms 53740 KB Output is correct
14 Correct 2582 ms 62060 KB Output is correct
15 Execution timed out 8022 ms 80936 KB Time limit exceeded
16 Execution timed out 8064 ms 104420 KB Time limit exceeded
17 Execution timed out 8101 ms 93316 KB Time limit exceeded