oj.uz

답안 #899717

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
899717 2024-01-06T22:45:44 Z boyliguanhan Regions (IOI09_regions) C++17
75 / 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[450];
unordered_map<int,int> ans1[450];
unordered_map<int,array<int,450>> ans2;
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;
}
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]>450)
            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 2 ms 8792 KB Output is correct
2 Correct 2 ms 8792 KB Output is correct
3 Correct 2 ms 8792 KB Output is correct
4 Correct 5 ms 8792 KB Output is correct
5 Correct 7 ms 8792 KB Output is correct
6 Correct 13 ms 9304 KB Output is correct
7 Correct 23 ms 9048 KB Output is correct
8 Correct 29 ms 9304 KB Output is correct
9 Correct 49 ms 10952 KB Output is correct
10 Correct 94 ms 10072 KB Output is correct
11 Correct 152 ms 10288 KB Output is correct
12 Correct 173 ms 11760 KB Output is correct
13 Correct 201 ms 10620 KB Output is correct
14 Correct 281 ms 11296 KB Output is correct
15 Correct 387 ms 22616 KB Output is correct

Subtask #2
60.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 874 ms 17448 KB Output is correct
2 Correct 1008 ms 13284 KB Output is correct
3 Correct 1749 ms 22656 KB Output is correct
4 Correct 311 ms 17472 KB Output is correct
5 Correct 395 ms 21480 KB Output is correct
6 Correct 919 ms 41268 KB Output is correct
7 Correct 1224 ms 37344 KB Output is correct
8 Execution timed out 8051 ms 82500 KB Time limit exceeded
9 Correct 2079 ms 47192 KB Output is correct
10 Runtime error 6777 ms 131072 KB Execution killed with signal 9
11 Correct 3191 ms 59132 KB Output is correct
12 Correct 1823 ms 47400 KB Output is correct
13 Correct 2577 ms 50280 KB Output is correct
14 Correct 3243 ms 67416 KB Output is correct
15 Execution timed out 8057 ms 85352 KB Time limit exceeded
16 Execution timed out 8067 ms 113320 KB Time limit exceeded
17 Execution timed out 8058 ms 97564 KB Time limit exceeded