oj.uz

Submission #899713

# Submission time Handle Problem Language Result Execution time Memory
899713 2024-01-06T22:42:01 Z boyliguanhan Regions (IOI09_regions) C++17
85 / 100
 8000 ms 86100 KB 
#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace __gnu_pbds;
#pragma GCC optimize(2)
#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;
}
void print(int num){
    if(num<0){
        putchar('-');
        num*=-1;
    }
    if(num>9) {
        print(num/10);
    }
    putchar((num%10)^48);
}
using namespace std;
vector<l> adj[200001];
vector<pair<l,l>> arr[25001];
l region[200001], t, in[200001], out[200001], li[200001], sz[25001], lg[401];
map<int,int> ans1[401];
map<int,array<int,401>> ans2;
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[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(){
    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]>500)
            lg[lr]=i, li[i]=++lr;
    dfs(1);
    while(q--){
        int r1=read(), r2=read();
        if(li[r1])
            print(ans1[li[r1]][r2]);
        else if(li[r2])
            print(ans2[r1][li[r2]]);
        else
            print(query_s(r1, r2));
        puts("");
        fflush(stdout);
    }
    return 0;
}

Compilation message

regions.cpp: In function 'int query_s(int, int)':
regions.cpp:57: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]
   57 |     while(a<arr[r1].size()||b<arr[r2].size()){
      |           ~^~~~~~~~~~~~~~~
regions.cpp:57: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]
   57 |     while(a<arr[r1].size()||b<arr[r2].size()){
      |                             ~^~~~~~~~~~~~~~~
regions.cpp:58: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]
   58 |         if(a<arr[r1].size()&&b<arr[r2].size()){
      |            ~^~~~~~~~~~~~~~~
regions.cpp:58: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]
   58 |         if(a<arr[r1].size()&&b<arr[r2].size()){
      |                              ~^~~~~~~~~~~~~~~
regions.cpp:63: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]
   63 |         } else if(a<arr[r1].size())
      |                   ~^~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 2 ms 8792 KB Output is correct
3 Correct 2 ms 8792 KB Output is correct
4 Correct 3 ms 8792 KB Output is correct
5 Correct 6 ms 8792 KB Output is correct
6 Correct 14 ms 9304 KB Output is correct
7 Correct 21 ms 9184 KB Output is correct
8 Correct 25 ms 9304 KB Output is correct
9 Correct 58 ms 10584 KB Output is correct
10 Correct 96 ms 10104 KB Output is correct
11 Correct 163 ms 10464 KB Output is correct
12 Correct 214 ms 11600 KB Output is correct
13 Correct 221 ms 10328 KB Output is correct
14 Correct 286 ms 11020 KB Output is correct
15 Correct 500 ms 19864 KB Output is correct

Subtask #2
70.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1083 ms 16404 KB Output is correct
2 Correct 1040 ms 13160 KB Output is correct
3 Correct 2063 ms 21232 KB Output is correct
4 Correct 354 ms 16824 KB Output is correct
5 Correct 513 ms 20700 KB Output is correct
6 Correct 1053 ms 22896 KB Output is correct
7 Correct 1401 ms 30068 KB Output is correct
8 Correct 1693 ms 45100 KB Output is correct
9 Correct 2579 ms 43944 KB Output is correct
10 Correct 4003 ms 76028 KB Output is correct
11 Correct 3925 ms 54952 KB Output is correct
12 Correct 2987 ms 45320 KB Output is correct
13 Correct 6264 ms 46840 KB Output is correct
14 Correct 7350 ms 65784 KB Output is correct
15 Execution timed out 8031 ms 61624 KB Time limit exceeded
16 Execution timed out 8090 ms 86100 KB Time limit exceeded
17 Execution timed out 8013 ms 80860 KB Time limit exceeded