답안 #899689

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
899689 2024-01-06T21:27:53 Z boyliguanhan Regions (IOI09_regions) C++17
0 / 100
2380 ms 131072 KB
#include<bits/stdc++.h>
#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(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;
    b.clear();
}
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],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 'std::unordered_map<int, int>& dfs(int)':
regions.cpp:49:12: warning: reference to local variable 'cur' returned [-Wreturn-local-addr]
   49 |     return cur;
      |            ^~~
regions.cpp:34:24: note: declared here
   34 |     unordered_map<l,l> cur;
      |                        ^~~
regions.cpp: In function 'int query_s(int, int)':
regions.cpp:54: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]
   54 |     while(a<arr[r1].size()||b<arr[r2].size()){
      |           ~^~~~~~~~~~~~~~~
regions.cpp:54: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]
   54 |     while(a<arr[r1].size()||b<arr[r2].size()){
      |                             ~^~~~~~~~~~~~~~~
regions.cpp:55: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]
   55 |         if(a<arr[r1].size()&&b<arr[r2].size()){
      |            ~^~~~~~~~~~~~~~~
regions.cpp:55: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]
   55 |         if(a<arr[r1].size()&&b<arr[r2].size()){
      |                              ~^~~~~~~~~~~~~~~
regions.cpp:60: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]
   60 |         } 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 21592 KB Execution killed with signal 11
3 Runtime error 10 ms 21644 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 10 ms 22148 KB Execution killed with signal 11
7 Runtime error 10 ms 21592 KB Execution killed with signal 11
8 Runtime error 11 ms 21592 KB Execution killed with signal 11
9 Runtime error 12 ms 24920 KB Execution killed with signal 11
10 Runtime error 10 ms 22104 KB Execution killed with signal 11
11 Runtime error 11 ms 22616 KB Execution killed with signal 11
12 Runtime error 11 ms 23028 KB Execution killed with signal 11
13 Runtime error 12 ms 22360 KB Execution killed with signal 11
14 Runtime error 13 ms 23516 KB Execution killed with signal 11
15 Runtime error 31 ms 49292 KB Execution killed with signal 11
# 결과 실행 시간 메모리 Grader output
1 Runtime error 16 ms 27040 KB Execution killed with signal 11
2 Runtime error 21 ms 24580 KB Execution killed with signal 11
3 Runtime error 31 ms 36016 KB Execution killed with signal 11
4 Runtime error 12 ms 23272 KB Execution killed with signal 11
5 Runtime error 15 ms 24312 KB Execution killed with signal 11
6 Runtime error 14 ms 24552 KB Execution killed with signal 11
7 Runtime error 17 ms 25300 KB Execution killed with signal 11
8 Runtime error 23 ms 33272 KB Execution killed with signal 11
9 Runtime error 25 ms 30844 KB Execution killed with signal 11
10 Runtime error 32 ms 33880 KB Execution killed with signal 11
11 Runtime error 36 ms 29328 KB Execution killed with signal 11
12 Runtime error 30 ms 33824 KB Execution killed with signal 11
13 Runtime error 32 ms 33184 KB Execution killed with signal 11
14 Runtime error 35 ms 32652 KB Execution killed with signal 11
15 Runtime error 38 ms 45320 KB Execution killed with signal 11
16 Runtime error 2380 ms 131072 KB Execution killed with signal 9
17 Runtime error 32 ms 34912 KB Execution killed with signal 11