oj.uz

Submission #687021

# Submission time Handle Problem Language Result Execution time Memory
687021 2023-01-26T05:06:06 Z boyliguanhan Regions (IOI09_regions) C++17
13 / 100
 202 ms 24588 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[25001], 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
13.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5584 KB Output is correct
2 Correct 4 ms 5584 KB Output is correct
3 Correct 7 ms 5584 KB Output is correct
4 Correct 6 ms 5584 KB Output is correct
5 Correct 11 ms 5584 KB Output is correct
6 Correct 27 ms 5840 KB Output is correct
7 Correct 31 ms 5712 KB Output is correct
8 Correct 24 ms 5840 KB Output is correct
9 Correct 48 ms 7120 KB Output is correct
10 Correct 101 ms 6736 KB Output is correct
11 Correct 135 ms 7364 KB Output is correct
12 Correct 176 ms 8664 KB Output is correct
13 Correct 202 ms 8080 KB Output is correct
14 Runtime error 25 ms 13136 KB Execution killed with signal 11
15 Runtime error 36 ms 14116 KB Execution killed with signal 11

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 55 ms 15980 KB Execution killed with signal 11
2 Runtime error 58 ms 14980 KB Execution killed with signal 11
3 Runtime error 59 ms 17104 KB Execution killed with signal 11
4 Runtime error 35 ms 13080 KB Execution killed with signal 11
5 Runtime error 31 ms 13864 KB Execution killed with signal 11
6 Runtime error 40 ms 14364 KB Execution killed with signal 11
7 Runtime error 51 ms 15400 KB Execution killed with signal 11
8 Runtime error 67 ms 17956 KB Execution killed with signal 11
9 Runtime error 93 ms 20568 KB Execution killed with signal 11
10 Runtime error 112 ms 22656 KB Execution killed with signal 11
11 Runtime error 133 ms 20116 KB Execution killed with signal 11
12 Runtime error 138 ms 23616 KB Execution killed with signal 11
13 Runtime error 121 ms 22600 KB Execution killed with signal 11
14 Runtime error 126 ms 22492 KB Execution killed with signal 11
15 Runtime error 125 ms 24588 KB Execution killed with signal 11
16 Runtime error 176 ms 24560 KB Execution killed with signal 11
17 Runtime error 139 ms 24416 KB Execution killed with signal 11