oj.uz

Submission #687203

# Submission time Handle Problem Language Result Execution time Memory
687203 2023-01-26T07:38:08 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;
    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:42: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]
   42 |     while(a<arr[r1].size()||b<arr[r2].size()){
      |           ~^~~~~~~~~~~~~~~
regions.cpp:42: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]
   42 |     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 11080 KB Execution killed with signal 11
3 Runtime error 11 ms 11128 KB Execution killed with signal 11
4 Incorrect 10 ms 5624 KB Output isn't correct
5 Incorrect 9 ms 5584 KB Output isn't correct
6 Runtime error 13 ms 11692 KB Execution killed with signal 11
7 Incorrect 33 ms 5712 KB Output isn't correct
8 Runtime error 9 ms 11704 KB Execution killed with signal 11
9 Runtime error 19 ms 14664 KB Execution killed with signal 11
10 Incorrect 115 ms 6404 KB Output isn't correct
11 Incorrect 130 ms 6856 KB Output isn't correct
12 Incorrect 126 ms 8016 KB Output isn't correct
13 Incorrect 175 ms 7076 KB Output isn't correct
14 Runtime error 33 ms 15708 KB Execution killed with signal 11
15 Incorrect 286 ms 19016 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 2378 ms 14516 KB Output isn't correct
2 Runtime error 72 ms 21084 KB Execution killed with signal 11
3 Incorrect 2472 ms 20028 KB Output isn't correct
4 Runtime error 40 ms 17092 KB Execution killed with signal 11
5 Runtime error 43 ms 30648 KB Execution killed with signal 11
6 Runtime error 66 ms 22732 KB Execution killed with signal 11
7 Runtime error 220 ms 24840 KB Execution killed with signal 11
8 Runtime error 720 ms 65100 KB Execution killed with signal 11
9 Runtime error 147 ms 46676 KB Execution killed with signal 11
10 Runtime error 170 ms 91060 KB Execution killed with signal 11
11 Runtime error 218 ms 41816 KB Execution killed with signal 11
12 Runtime error 304 ms 43436 KB Execution killed with signal 11
13 Runtime error 651 ms 49624 KB Execution killed with signal 11
14 Runtime error 534 ms 47196 KB Execution killed with signal 11
15 Incorrect 7904 ms 41272 KB Output isn't correct
16 Execution timed out 8041 ms 74260 KB Time limit exceeded
17 Execution timed out 8032 ms 131072 KB Time limit exceeded