oj.uz

Submission #899691

# Submission time Handle Problem Language Result Execution time Memory
899691 2024-01-06T21:30:23 Z boyliguanhan Regions (IOI09_regions) C++17
60 / 100
 8000 ms 90592 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]>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 10584 KB Output is correct
2 Correct 2 ms 10840 KB Output is correct
3 Correct 2 ms 10672 KB Output is correct
4 Correct 4 ms 10840 KB Output is correct
5 Correct 7 ms 10840 KB Output is correct
6 Correct 20 ms 11164 KB Output is correct
7 Correct 19 ms 10840 KB Output is correct
8 Correct 21 ms 10840 KB Output is correct
9 Correct 111 ms 12868 KB Output is correct
10 Correct 72 ms 11524 KB Output is correct
11 Correct 112 ms 12116 KB Output is correct
12 Correct 366 ms 13328 KB Output is correct
13 Correct 141 ms 11984 KB Output is correct
14 Correct 212 ms 12856 KB Output is correct
15 Correct 641 ms 26972 KB Output is correct

Subtask #2
45.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1202 ms 22236 KB Output is correct
2 Correct 934 ms 17000 KB Output is correct
3 Correct 2589 ms 29092 KB Output is correct
4 Correct 697 ms 13596 KB Output is correct
5 Correct 4141 ms 21672 KB Output is correct
6 Correct 3315 ms 16492 KB Output is correct
7 Correct 5100 ms 17128 KB Output is correct
8 Execution timed out 8100 ms 41176 KB Time limit exceeded
9 Execution timed out 8044 ms 27192 KB Time limit exceeded
10 Execution timed out 8093 ms 32220 KB Time limit exceeded
11 Correct 7761 ms 26524 KB Output is correct
12 Correct 5797 ms 27332 KB Output is correct
13 Execution timed out 8054 ms 28828 KB Time limit exceeded
14 Execution timed out 8082 ms 29608 KB Time limit exceeded
15 Execution timed out 8077 ms 46416 KB Time limit exceeded
16 Execution timed out 8051 ms 90592 KB Time limit exceeded
17 Execution timed out 8096 ms 81752 KB Time limit exceeded