답안 #899686

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
899686 2024-01-06T21:17:40 Z boyliguanhan Regions (IOI09_regions) C++17
0 / 100
2248 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[21][25001], ans2[25001][21], in[200001], out[200001], li[200001], sz[25001], lg[21];
void merge(gp_hash_table<l, l> &a, gp_hash_table<l, l> &b){
    if(a.size()<b.size())
        swap(a, b);
    for(auto i: b)
        a[i.first]+=i.second;
}
gp_hash_table<l,l>& dfs(l n){
    gp_hash_table<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]>10000)
            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 '__gnu_pbds::gp_hash_table<int, int>& dfs(int)':
regions.cpp:50:12: warning: reference to local variable 'cur' returned [-Wreturn-local-addr]
   50 |     return cur;
      |            ^~~
regions.cpp:35:24: note: declared here
   35 |     gp_hash_table<l,l> cur;
      |                        ^~~
regions.cpp: In function 'int query_s(int, int)':
regions.cpp:55: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]
   55 |     while(a<arr[r1].size()||b<arr[r2].size()){
      |           ~^~~~~~~~~~~~~~~
regions.cpp:55: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]
   55 |     while(a<arr[r1].size()||b<arr[r2].size()){
      |                             ~^~~~~~~~~~~~~~~
regions.cpp:56: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]
   56 |         if(a<arr[r1].size()&&b<arr[r2].size()){
      |            ~^~~~~~~~~~~~~~~
regions.cpp:56: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]
   56 |         if(a<arr[r1].size()&&b<arr[r2].size()){
      |                              ~^~~~~~~~~~~~~~~
regions.cpp:61: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]
   61 |         } else if(a<arr[r1].size())
      |                   ~^~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Runtime error 10 ms 21592 KB Execution killed with signal 11
2 Runtime error 10 ms 21532 KB Execution killed with signal 11
3 Runtime error 9 ms 21592 KB Execution killed with signal 11
4 Runtime error 9 ms 21592 KB Execution killed with signal 11
5 Runtime error 10 ms 21592 KB Execution killed with signal 11
6 Runtime error 12 ms 22104 KB Execution killed with signal 11
7 Runtime error 9 ms 21592 KB Execution killed with signal 11
8 Runtime error 10 ms 21592 KB Execution killed with signal 11
9 Runtime error 15 ms 25300 KB Execution killed with signal 11
10 Runtime error 10 ms 22176 KB Execution killed with signal 11
11 Runtime error 13 ms 22712 KB Execution killed with signal 11
12 Runtime error 11 ms 22872 KB Execution killed with signal 11
13 Runtime error 12 ms 22360 KB Execution killed with signal 11
14 Runtime error 14 ms 23516 KB Execution killed with signal 11
15 Runtime error 33 ms 50496 KB Execution killed with signal 11
# 결과 실행 시간 메모리 Grader output
1 Runtime error 17 ms 26608 KB Execution killed with signal 11
2 Runtime error 17 ms 25332 KB Execution killed with signal 11
3 Runtime error 25 ms 36404 KB Execution killed with signal 11
4 Runtime error 13 ms 23128 KB Execution killed with signal 11
5 Runtime error 14 ms 24112 KB Execution killed with signal 11
6 Runtime error 14 ms 24144 KB Execution killed with signal 11
7 Runtime error 16 ms 25796 KB Execution killed with signal 11
8 Runtime error 23 ms 33352 KB Execution killed with signal 11
9 Runtime error 24 ms 30832 KB Execution killed with signal 11
10 Runtime error 31 ms 34576 KB Execution killed with signal 11
11 Runtime error 37 ms 29288 KB Execution killed with signal 11
12 Runtime error 30 ms 34640 KB Execution killed with signal 11
13 Runtime error 30 ms 33036 KB Execution killed with signal 11
14 Runtime error 31 ms 32128 KB Execution killed with signal 11
15 Runtime error 40 ms 46044 KB Execution killed with signal 11
16 Runtime error 2248 ms 131072 KB Execution killed with signal 9
17 Runtime error 30 ms 34816 KB Execution killed with signal 11