oj.uz

Submission #703093

# Submission time Handle Problem Language Result Execution time Memory
703093 2023-02-26T04:18:10 Z boyliguanhan Regions (IOI09_regions) C++17
90 / 100
 8000 ms 74396 KB 
#include<bits/stdc++.h>
#pragma GCC optimize(2)
#define l int
int read(){
    char x = getchar_unlocked();
    int val = 0;
    while(x<'0'||x>'9')x=getchar_unlocked();
    while('0'<=x&&x<='9')
        val = val*10+x-'0', x=getchar_unlocked();
    return val;
}
using namespace std;
vector<l> adj[200001];
vector<pair<l,l>> arr[25001];
l region[200001], t, ans1[21][25001], ans2[25001][21], in[200001], out[200001], li[200001], sz[25001], lg[21];
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],-1});
    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;
    while(a<arr[r1].size()&&b<arr[r2].size()){
        if(arr[r1][a]<arr[r2][b])
            o+=arr[r1][a].second, a++;
        else
            sum+=o, b++;
    }
    return sum/2;
}
int main(){
    l n=read(), r=read(), q=read(), lr=0;
    region[1]=read();
    for(l i = 2; i <= n; i++){
        adj[read()].push_back(i);
        region[i] = read();
        sz[region[i]]++;
    }
    for(int i = 1; i <= r; i++)
        if(sz[i]>10000)
            lg[lr]=i, li[i]=++lr;
    dfs(1);
    while(q--){
        int r1=read(), r2=read();
        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:42: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]
   42 |     while(a<arr[r1].size()&&b<arr[r2].size()){
      |           ~^~~~~~~~~~~~~~~
regions.cpp:42: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]
   42 |     while(a<arr[r1].size()&&b<arr[r2].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 4 ms 5584 KB Output is correct
4 Correct 7 ms 5584 KB Output is correct
5 Correct 8 ms 5584 KB Output is correct
6 Correct 18 ms 5840 KB Output is correct
7 Correct 26 ms 5712 KB Output is correct
8 Correct 42 ms 5840 KB Output is correct
9 Correct 44 ms 7376 KB Output is correct
10 Correct 69 ms 6352 KB Output is correct
11 Correct 101 ms 6864 KB Output is correct
12 Correct 75 ms 8064 KB Output is correct
13 Correct 167 ms 7076 KB Output is correct
14 Correct 201 ms 7888 KB Output is correct
15 Correct 252 ms 19020 KB Output is correct

Subtask #2
75.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1742 ms 14588 KB Output is correct
2 Correct 2396 ms 10544 KB Output is correct
3 Correct 1784 ms 19948 KB Output is correct
4 Correct 283 ms 8528 KB Output is correct
5 Correct 346 ms 15252 KB Output is correct
6 Correct 771 ms 11428 KB Output is correct
7 Correct 977 ms 12400 KB Output is correct
8 Correct 1034 ms 32220 KB Output is correct
9 Correct 1480 ms 23240 KB Output is correct
10 Correct 2386 ms 45496 KB Output is correct
11 Correct 2568 ms 21152 KB Output is correct
12 Correct 1028 ms 21664 KB Output is correct
13 Correct 1639 ms 24604 KB Output is correct
14 Correct 1742 ms 23608 KB Output is correct
15 Correct 6411 ms 41416 KB Output is correct
16 Execution timed out 8077 ms 74396 KB Time limit exceeded
17 Execution timed out 8032 ms 66080 KB Time limit exceeded