oj.uz

Submission #687197

# Submission time Handle Problem Language Result Execution time Memory
687197 2023-01-26T07:35:16 Z boyliguanhan Regions (IOI09_regions) C++17
0 / 100
 8000 ms 131072 KB 
#include<bits/stdc++.h>
#pragma GCC optimize(3)
#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;
}
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;
}
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],-1});
    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(arr[r1][a]<arr[r2][b])
            o+=arr[r1][a].second, a++;
        else
            sum+=o, b++;
    }
    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])
            cout << ans1[li[r1]][r2] << endl;
        else if(li[r2])
            cout << ans2[r1][li[r2]] << endl;
        else
            cout << query_s(r1, r2) << endl;
    }
    return 0;
}

Compilation message

regions.cpp: In function 'int query_s(int, int)':
regions.cpp:43: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]
   43 |     while(a<arr[r1].size()||b<arr[r2].size()){
      |           ~^~~~~~~~~~~~~~~
regions.cpp:43: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]
   43 |     while(a<arr[r1].size()||b<arr[r2].size()){
      |                             ~^~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 11088 KB Execution killed with signal 11
2 Runtime error 10 ms 11120 KB Execution killed with signal 11
3 Runtime error 11 ms 11216 KB Execution killed with signal 11
4 Incorrect 8 ms 5584 KB Output isn't correct
5 Incorrect 11 ms 5584 KB Output isn't correct
6 Runtime error 9 ms 11756 KB Execution killed with signal 11
7 Incorrect 26 ms 5712 KB Output isn't correct
8 Runtime error 11 ms 11624 KB Execution killed with signal 11
9 Runtime error 15 ms 14684 KB Execution killed with signal 11
10 Incorrect 76 ms 6352 KB Output isn't correct
11 Incorrect 128 ms 6860 KB Output isn't correct
12 Incorrect 140 ms 7972 KB Output isn't correct
13 Incorrect 176 ms 7076 KB Output isn't correct
14 Runtime error 27 ms 15708 KB Execution killed with signal 11
15 Incorrect 191 ms 19104 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 2283 ms 14516 KB Output isn't correct
2 Runtime error 69 ms 21184 KB Execution killed with signal 11
3 Incorrect 2370 ms 20000 KB Output isn't correct
4 Runtime error 39 ms 17128 KB Execution killed with signal 11
5 Runtime error 42 ms 30664 KB Execution killed with signal 11
6 Runtime error 51 ms 22784 KB Execution killed with signal 11
7 Runtime error 225 ms 24928 KB Execution killed with signal 11
8 Runtime error 777 ms 65084 KB Execution killed with signal 11
9 Runtime error 161 ms 46704 KB Execution killed with signal 11
10 Runtime error 206 ms 91020 KB Execution killed with signal 11
11 Runtime error 218 ms 41896 KB Execution killed with signal 11
12 Runtime error 283 ms 43440 KB Execution killed with signal 11
13 Runtime error 654 ms 49544 KB Execution killed with signal 11
14 Runtime error 542 ms 47196 KB Execution killed with signal 11
15 Incorrect 7523 ms 41148 KB Output isn't correct
16 Execution timed out 8099 ms 74392 KB Time limit exceeded
17 Runtime error 7966 ms 131072 KB Execution killed with signal 11