oj.uz

Submission #899694

# Submission time Handle Problem Language Result Execution time Memory
899694 2024-01-06T21:32:10 Z boyliguanhan Regions (IOI09_regions) C++17
65 / 100
 8000 ms 131072 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, ans1[101][25001], ans2[25001][101], in[200001], out[200001], li[200001], sz[25001], lg[101];
gp_hash_table<l,l> dfs(l n){
    gp_hash_table<l,l> cur, nxt;
    cur[region[n]]=1;
    in[n]=t++;
    arr[region[n]].push_back({in[n],1});
    for(auto i: adj[n]){
        nxt = dfs(i);
        if(nxt.size()<cur.size())
            swap(nxt, cur);
        for(auto i: nxt)
            cur[i.first]+=i.second;
    }
    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]>1000)
            lg[lr]=i, li[i]=++lr;
    dfs(1);
    while(q--){
        int r1=read(), r2=read();
        if(li[r1])
            print(ans1[li[r1]][r2]),cout<<endl;
        else if(li[r2])
            print(ans2[r1][li[r2]]),cout<<endl;
        else
            print(query_s(r1, r2)),cout<<endl;
    }
    return 0;
}

Compilation message

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

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12372 KB Output is correct
2 Correct 2 ms 12120 KB Output is correct
3 Correct 4 ms 12120 KB Output is correct
4 Correct 4 ms 12120 KB Output is correct
5 Correct 6 ms 12120 KB Output is correct
6 Correct 19 ms 12632 KB Output is correct
7 Correct 29 ms 12120 KB Output is correct
8 Correct 28 ms 12376 KB Output is correct
9 Correct 84 ms 16348 KB Output is correct
10 Correct 71 ms 12764 KB Output is correct
11 Correct 112 ms 13552 KB Output is correct
12 Correct 271 ms 16716 KB Output is correct
13 Correct 159 ms 13268 KB Output is correct
14 Correct 218 ms 14224 KB Output is correct
15 Correct 491 ms 45656 KB Output is correct

Subtask #2
50.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1170 ms 32152 KB Output is correct
2 Correct 902 ms 21120 KB Output is correct
3 Correct 2265 ms 47596 KB Output is correct
4 Correct 468 ms 15484 KB Output is correct
5 Correct 3567 ms 36360 KB Output is correct
6 Correct 2063 ms 22032 KB Output is correct
7 Correct 3169 ms 25076 KB Output is correct
8 Execution timed out 8054 ms 76400 KB Time limit exceeded
9 Execution timed out 8012 ms 42224 KB Time limit exceeded
10 Execution timed out 8034 ms 54412 KB Time limit exceeded
11 Correct 5749 ms 35356 KB Output is correct
12 Correct 3615 ms 38324 KB Output is correct
13 Execution timed out 8086 ms 47900 KB Time limit exceeded
14 Correct 6988 ms 43128 KB Output is correct
15 Execution timed out 8083 ms 87292 KB Time limit exceeded
16 Runtime error 108 ms 131072 KB Execution killed with signal 9
17 Runtime error 336 ms 131072 KB Execution killed with signal 9