oj.uz

Submission #899690

# Submission time Handle Problem Language Result Execution time Memory
899690 2024-01-06T21:29:32 Z boyliguanhan Regions (IOI09_regions) C++17
60 / 100
 8000 ms 90584 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[21][25001], ans2[25001][21], in[200001], out[200001], li[200001], sz[25001], lg[21];
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]>10000)
            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 10840 KB Output is correct
2 Correct 2 ms 10840 KB Output is correct
3 Correct 2 ms 10840 KB Output is correct
4 Correct 5 ms 10840 KB Output is correct
5 Correct 6 ms 10840 KB Output is correct
6 Correct 16 ms 11096 KB Output is correct
7 Correct 19 ms 10840 KB Output is correct
8 Correct 20 ms 10840 KB Output is correct
9 Correct 101 ms 12632 KB Output is correct
10 Correct 62 ms 11352 KB Output is correct
11 Correct 106 ms 12048 KB Output is correct
12 Correct 364 ms 13272 KB Output is correct
13 Correct 132 ms 12000 KB Output is correct
14 Correct 187 ms 12856 KB Output is correct
15 Correct 674 ms 26968 KB Output is correct

Subtask #2
45.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 3001 ms 22360 KB Output is correct
2 Correct 4165 ms 18204 KB Output is correct
3 Correct 3135 ms 29124 KB Output is correct
4 Correct 609 ms 13600 KB Output is correct
5 Correct 4098 ms 21848 KB Output is correct
6 Correct 3149 ms 16768 KB Output is correct
7 Correct 4291 ms 17048 KB Output is correct
8 Execution timed out 8032 ms 40932 KB Time limit exceeded
9 Execution timed out 8012 ms 27056 KB Time limit exceeded
10 Execution timed out 8090 ms 31964 KB Time limit exceeded
11 Correct 7812 ms 26588 KB Output is correct
12 Correct 5471 ms 27340 KB Output is correct
13 Execution timed out 8006 ms 28660 KB Time limit exceeded
14 Execution timed out 8009 ms 29224 KB Time limit exceeded
15 Execution timed out 8087 ms 46732 KB Time limit exceeded
16 Execution timed out 8087 ms 90584 KB Time limit exceeded
17 Execution timed out 8100 ms 81772 KB Time limit exceeded