oj.uz

Submission #687155

# Submission time Handle Problem Language Result Execution time Memory
687155 2023-01-26T06:59:25 Z boyliguanhan Regions (IOI09_regions) C++17
90 / 100
 8000 ms 75240 KB 
#include<bits/stdc++.h>
#pragma GCC optimize(2)
#define l int
using namespace std;
vector<l> adj[200001], lg;
vector<pair<l,l>> arr[25001];
l region[200001], t, ans1[30][25001], ans2[25001][30], in[200001], out[200001], li[200001], sz[25001];
void merge(unordered_map<l, l> &a, unordered_map<l, l> b){
    if(a.size()<b.size())
        swap(a, b);
    for(auto i: b)
        a[i.first]+=i.second;
}
unordered_map<l,l> dfs(l n){
    unordered_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(){
    iostream::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.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]>5000)
            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 'int query_s(int, int)':
regions.cpp:35:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, 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: 'int' and 'std::vector<std::pair<int, 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: 'int' and 'std::vector<std::pair<int, 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: 'int' and 'std::vector<std::pair<int, 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: 'int' and 'std::vector<std::pair<int, 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 3 ms 5616 KB Output is correct
2 Correct 4 ms 5584 KB Output is correct
3 Correct 6 ms 5584 KB Output is correct
4 Correct 8 ms 5584 KB Output is correct
5 Correct 12 ms 5584 KB Output is correct
6 Correct 24 ms 5840 KB Output is correct
7 Correct 31 ms 5756 KB Output is correct
8 Correct 42 ms 5840 KB Output is correct
9 Correct 53 ms 7376 KB Output is correct
10 Correct 88 ms 6352 KB Output is correct
11 Correct 105 ms 6952 KB Output is correct
12 Correct 164 ms 8048 KB Output is correct
13 Correct 149 ms 7072 KB Output is correct
14 Correct 259 ms 7868 KB Output is correct
15 Correct 317 ms 19084 KB Output is correct

Subtask #2
75.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1150 ms 14664 KB Output is correct
2 Correct 1120 ms 10636 KB Output is correct
3 Correct 2175 ms 20008 KB Output is correct
4 Correct 286 ms 8256 KB Output is correct
5 Correct 365 ms 14836 KB Output is correct
6 Correct 961 ms 10788 KB Output is correct
7 Correct 1129 ms 11608 KB Output is correct
8 Correct 1331 ms 31428 KB Output is correct
9 Correct 2079 ms 22000 KB Output is correct
10 Correct 3221 ms 43424 KB Output is correct
11 Correct 3410 ms 19072 KB Output is correct
12 Correct 1320 ms 22292 KB Output is correct
13 Correct 2319 ms 25140 KB Output is correct
14 Correct 2637 ms 24256 KB Output is correct
15 Correct 7553 ms 42048 KB Output is correct
16 Execution timed out 8064 ms 75240 KB Time limit exceeded
17 Execution timed out 8007 ms 66988 KB Time limit exceeded