oj.uz

Submission #687193

# Submission time Handle Problem Language Result Execution time Memory
687193 2023-01-26T07:31:50 Z boyliguanhan Regions (IOI09_regions) C++17
90 / 100
 8000 ms 74304 KB 
#include<bits/stdc++.h>
#pragma GCC optimize(3)
#define l int
int read(){
    char x = getchar();
    int val = 0;
    while(x<'0'||x>'9')x=getchar();
    while('0'<=x&&x<='9')
        val = val*10+x-'0', x=getchar();
    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;
    vector<int> v;
    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:43: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]
   43 |     while(a<arr[r1].size()&&b<arr[r2].size()){
      |           ~^~~~~~~~~~~~~~~
regions.cpp:43: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]
   43 |     while(a<arr[r1].size()&&b<arr[r2].size()){
      |                             ~^~~~~~~~~~~~~~~

Subtask #1
15.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 6 ms 5584 KB Output is correct
4 Correct 8 ms 5584 KB Output is correct
5 Correct 8 ms 5584 KB Output is correct
6 Correct 16 ms 5840 KB Output is correct
7 Correct 34 ms 5712 KB Output is correct
8 Correct 40 ms 5840 KB Output is correct
9 Correct 48 ms 7376 KB Output is correct
10 Correct 74 ms 6352 KB Output is correct
11 Correct 123 ms 6856 KB Output is correct
12 Correct 131 ms 8024 KB Output is correct
13 Correct 154 ms 7076 KB Output is correct
14 Correct 204 ms 7884 KB Output is correct
15 Correct 218 ms 19036 KB Output is correct

Subtask #2
75.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1957 ms 14516 KB Output is correct
2 Correct 2641 ms 10548 KB Output is correct
3 Correct 2008 ms 20040 KB Output is correct
4 Correct 237 ms 8520 KB Output is correct
5 Correct 313 ms 15240 KB Output is correct
6 Correct 823 ms 11348 KB Output is correct
7 Correct 963 ms 12400 KB Output is correct
8 Correct 832 ms 32208 KB Output is correct
9 Correct 1410 ms 23196 KB Output is correct
10 Correct 2188 ms 45428 KB Output is correct
11 Correct 2257 ms 21064 KB Output is correct
12 Correct 939 ms 21716 KB Output is correct
13 Correct 1870 ms 24580 KB Output is correct
14 Correct 2004 ms 23636 KB Output is correct
15 Correct 7226 ms 41284 KB Output is correct
16 Execution timed out 8090 ms 74304 KB Time limit exceeded
17 Execution timed out 8058 ms 66124 KB Time limit exceeded