oj.uz

답안 #899715

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
899715 2024-01-06T22:43:35 Z boyliguanhan Regions (IOI09_regions) C++17
70 / 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, in[200001], out[200001], li[200001], sz[25001], lg[401];
gp_hash_table<int,int> ans1[401];
gp_hash_table<int,array<int,401>> ans2;
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]>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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 8792 KB Output is correct
2 Correct 2 ms 8952 KB Output is correct
3 Correct 3 ms 9104 KB Output is correct
4 Correct 4 ms 9304 KB Output is correct
5 Correct 6 ms 9304 KB Output is correct
6 Correct 14 ms 10508 KB Output is correct
7 Correct 17 ms 10196 KB Output is correct
8 Correct 25 ms 10332 KB Output is correct
9 Correct 56 ms 13000 KB Output is correct
10 Correct 79 ms 11948 KB Output is correct
11 Correct 111 ms 12384 KB Output is correct
12 Correct 182 ms 13328 KB Output is correct
13 Correct 166 ms 12536 KB Output is correct
14 Correct 235 ms 11980 KB Output is correct
15 Correct 395 ms 24132 KB Output is correct

Subtask #2
55.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 948 ms 18368 KB Output is correct
2 Correct 888 ms 14028 KB Output is correct
3 Correct 1844 ms 24184 KB Output is correct
4 Correct 329 ms 30364 KB Output is correct
5 Correct 1188 ms 37420 KB Output is correct
6 Correct 1160 ms 51828 KB Output is correct
7 Correct 1731 ms 91464 KB Output is correct
8 Correct 7303 ms 112232 KB Output is correct
9 Correct 5269 ms 100744 KB Output is correct
10 Execution timed out 8021 ms 117792 KB Time limit exceeded
11 Runtime error 598 ms 131072 KB Execution killed with signal 9
12 Correct 2037 ms 99104 KB Output is correct
13 Correct 5522 ms 102632 KB Output is correct
14 Runtime error 1236 ms 131072 KB Execution killed with signal 9
15 Execution timed out 8026 ms 115944 KB Time limit exceeded
16 Runtime error 3695 ms 131072 KB Execution killed with signal 9
17 Runtime error 3493 ms 131072 KB Execution killed with signal 9