oj.uz

Submission #899692

# Submission time Handle Problem Language Result Execution time Memory
899692 2024-01-06T21:31:09 Z boyliguanhan Regions (IOI09_regions) C++17
60 / 100
 8000 ms 100184 KB 
#include<bits/stdc++.h>
#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, ans1[101][25001], ans2[25001][101], in[200001], out[200001], li[200001], sz[25001], lg[101];
unordered_map<l,l> dfs(l n){
    unordered_map<l,l> cur, nxt;
    cur[region[n]]=1;
    in[n]=t++;
    arr[region[n]].push_back({in[n],1});
    for(auto i: adj[n]){
        nxt = dfs(i);
        if(nxt.size()<cur.size())
            swap(nxt, cur);
        for(auto i: nxt)
            cur[i.first]+=i.second;
    }
    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:51: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]
   51 |     while(a<arr[r1].size()||b<arr[r2].size()){
      |           ~^~~~~~~~~~~~~~~
regions.cpp:51: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]
   51 |     while(a<arr[r1].size()||b<arr[r2].size()){
      |                             ~^~~~~~~~~~~~~~~
regions.cpp:52: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]
   52 |         if(a<arr[r1].size()&&b<arr[r2].size()){
      |            ~^~~~~~~~~~~~~~~
regions.cpp:52: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]
   52 |         if(a<arr[r1].size()&&b<arr[r2].size()){
      |                              ~^~~~~~~~~~~~~~~
regions.cpp:57: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]
   57 |         } else if(a<arr[r1].size())
      |                   ~^~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12124 KB Output is correct
2 Correct 4 ms 12120 KB Output is correct
3 Correct 4 ms 12120 KB Output is correct
4 Correct 4 ms 12120 KB Output is correct
5 Correct 6 ms 12120 KB Output is correct
6 Correct 18 ms 12376 KB Output is correct
7 Correct 17 ms 12120 KB Output is correct
8 Correct 29 ms 12120 KB Output is correct
9 Correct 105 ms 14164 KB Output is correct
10 Correct 83 ms 12932 KB Output is correct
11 Correct 154 ms 13056 KB Output is correct
12 Correct 378 ms 14552 KB Output is correct
13 Correct 140 ms 13392 KB Output is correct
14 Correct 223 ms 14140 KB Output is correct
15 Correct 684 ms 28264 KB Output is correct

Subtask #2
45.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1266 ms 25576 KB Output is correct
2 Correct 956 ms 20616 KB Output is correct
3 Correct 2589 ms 32472 KB Output is correct
4 Correct 702 ms 14884 KB Output is correct
5 Correct 4581 ms 25012 KB Output is correct
6 Correct 3349 ms 19860 KB Output is correct
7 Correct 4487 ms 22548 KB Output is correct
8 Execution timed out 8020 ms 46312 KB Time limit exceeded
9 Execution timed out 8026 ms 32248 KB Time limit exceeded
10 Execution timed out 8080 ms 39624 KB Time limit exceeded
11 Correct 7607 ms 34116 KB Output is correct
12 Correct 5759 ms 36932 KB Output is correct
13 Execution timed out 8096 ms 38152 KB Time limit exceeded
14 Execution timed out 8090 ms 38976 KB Time limit exceeded
15 Execution timed out 8101 ms 56252 KB Time limit exceeded
16 Execution timed out 8073 ms 100184 KB Time limit exceeded
17 Execution timed out 8073 ms 91672 KB Time limit exceeded