oj.uz

Submission #687025

# Submission time Handle Problem Language Result Execution time Memory
687025 2023-01-26T05:10:15 Z boyliguanhan Regions (IOI09_regions) C++17
55 / 100
 3044 ms 131072 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[501][25001], ans2[25001][501], 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]>500)
            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 9 ms 5584 KB Output is correct
4 Correct 9 ms 5548 KB Output is correct
5 Correct 12 ms 5584 KB Output is correct
6 Correct 22 ms 5840 KB Output is correct
7 Correct 32 ms 5712 KB Output is correct
8 Correct 43 ms 5840 KB Output is correct
9 Correct 57 ms 7096 KB Output is correct
10 Correct 92 ms 6736 KB Output is correct
11 Correct 134 ms 7476 KB Output is correct
12 Correct 147 ms 8668 KB Output is correct
13 Correct 136 ms 8080 KB Output is correct
14 Correct 276 ms 9144 KB Output is correct
15 Correct 282 ms 17472 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1215 ms 16796 KB Output isn't correct
2 Incorrect 1183 ms 13988 KB Output isn't correct
3 Incorrect 2005 ms 21864 KB Output isn't correct
4 Correct 339 ms 9488 KB Output is correct
5 Correct 392 ms 14492 KB Output is correct
6 Correct 1056 ms 12336 KB Output is correct
7 Correct 1211 ms 14200 KB Output is correct
8 Correct 1249 ms 30384 KB Output is correct
9 Correct 1970 ms 27032 KB Output is correct
10 Correct 2993 ms 42524 KB Output is correct
11 Correct 3044 ms 26856 KB Output is correct
12 Incorrect 1265 ms 82076 KB Output isn't correct
13 Incorrect 1797 ms 83984 KB Output isn't correct
14 Incorrect 2192 ms 98924 KB Output isn't correct
15 Runtime error 284 ms 131072 KB Execution killed with signal 9
16 Runtime error 214 ms 131072 KB Execution killed with signal 9
17 Runtime error 352 ms 131072 KB Execution killed with signal 9