oj.uz

답안 #899706

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
899706 2024-01-06T22:22:25 Z boyliguanhan Regions (IOI09_regions) C++17
80 / 100
 8000 ms 114240 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[201];
gp_hash_table<int,int> ans1[201];
gp_hash_table<int,array<int,201>> 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]>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: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 2 ms 8792 KB Output is correct
2 Correct 3 ms 8872 KB Output is correct
3 Correct 2 ms 8940 KB Output is correct
4 Correct 4 ms 9052 KB Output is correct
5 Correct 7 ms 9088 KB Output is correct
6 Correct 14 ms 9756 KB Output is correct
7 Correct 19 ms 9504 KB Output is correct
8 Correct 23 ms 9516 KB Output is correct
9 Correct 58 ms 11856 KB Output is correct
10 Correct 68 ms 10576 KB Output is correct
11 Correct 99 ms 11032 KB Output is correct
12 Correct 158 ms 12204 KB Output is correct
13 Correct 145 ms 11408 KB Output is correct
14 Correct 192 ms 11288 KB Output is correct
15 Correct 376 ms 23320 KB Output is correct

Subtask #2
65.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 909 ms 17604 KB Output is correct
2 Correct 869 ms 13636 KB Output is correct
3 Correct 1786 ms 23400 KB Output is correct
4 Correct 304 ms 20832 KB Output is correct
5 Correct 1216 ms 27796 KB Output is correct
6 Correct 1146 ms 32568 KB Output is correct
7 Correct 1676 ms 52768 KB Output is correct
8 Correct 7133 ms 73560 KB Output is correct
9 Correct 5134 ms 62208 KB Output is correct
10 Execution timed out 8103 ms 79312 KB Time limit exceeded
11 Correct 3505 ms 97600 KB Output is correct
12 Correct 1808 ms 60440 KB Output is correct
13 Correct 5454 ms 64132 KB Output is correct
14 Correct 3437 ms 112684 KB Output is correct
15 Execution timed out 8016 ms 77348 KB Time limit exceeded
16 Execution timed out 8032 ms 114240 KB Time limit exceeded
17 Execution timed out 8102 ms 109468 KB Time limit exceeded