oj.uz

Submission #895336

# Submission time Handle Problem Language Result Execution time Memory
895336 2023-12-29T19:02:01 Z Ahmed57 Regions (IOI09_regions) C++17
0 / 100
 43 ms 23624 KB 
#include <bits/stdc++.h>
 
using namespace std;
long long frq[25001],a3[25001];
int xd[25001],x,p,lol[200001],j,a,b,B = 500;
map<pair<int,int>,long long> mp;
vector<int> adj[200001];
vector<pair<int,int>> lo,qu[25001];
set<int> qu2[200001];
long long ans[200001];
void dfs(int i){
    frq[lol[i]]++;
    a3[lol[i]]++;
    for(j = 0;j<qu[lol[i]].size();j++){
        //cout<<i<<" "<<qu[i][j].first<<" "<<qu[i][j].second<<endl;
        ans[qu[lol[i]][j].second] += frq[qu[lol[i]][j].first];
    }
    for(auto e:qu2[lol[i]]){
        mp[{lol[i],e}] -=a3[e];
    }
    for(int w = 0;w<adj[i].size();w++){
        dfs(adj[i][w]);
    }
    for(auto e:qu2[lol[i]]){
        mp[{lol[i],e}] +=a3[e];
    }
    frq[lol[i]]--;
}
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    //freopen("input.txt","r",stdin);
    //freopen("outout.txt","w",stdout);
    int n,r,q;cin>>n>>r>>q;
    cin>>x;xd[x]++;
    lol[1] = x;
    for(int i = 2;i<=n;i++){
        cin>>p>>x;
        xd[x]++;
        lol[i] = x;
        adj[p].push_back(i);
    }
    for(int i = 1;i<=q;i++){
        cin>>a>>b;
        if(xd[b]<B){
            qu[b].push_back({a,i});
            ans[i] = 0;
        }else{
            lo.push_back({a,b});
            qu2[a].insert(b);
            ans[i] = -1;
        }
    }
    dfs(1);
    for(int i = 1;i<=q;i++){
        if(ans[i]==-1){
            ans[i] = mp[{lo[i-1].first,lo[i-1].second}];
        }cout<<ans[i]<<"\n";
    }
}

Compilation message

regions.cpp: In function 'void dfs(int)':
regions.cpp:14:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |     for(j = 0;j<qu[lol[i]].size();j++){
      |               ~^~~~~~~~~~~~~~~~~~
regions.cpp:21:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for(int w = 0;w<adj[i].size();w++){
      |                   ~^~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3 ms 16728 KB Time limit exceeded (wall clock)
2 Execution timed out 3 ms 16728 KB Time limit exceeded (wall clock)
3 Execution timed out 6 ms 16728 KB Time limit exceeded (wall clock)
4 Execution timed out 3 ms 16728 KB Time limit exceeded (wall clock)
5 Execution timed out 3 ms 16728 KB Time limit exceeded (wall clock)
6 Execution timed out 7 ms 16728 KB Time limit exceeded (wall clock)
7 Execution timed out 4 ms 16728 KB Time limit exceeded (wall clock)
8 Execution timed out 3 ms 16728 KB Time limit exceeded (wall clock)
9 Execution timed out 3 ms 16984 KB Time limit exceeded (wall clock)
10 Execution timed out 4 ms 16984 KB Time limit exceeded (wall clock)
11 Execution timed out 5 ms 17240 KB Time limit exceeded (wall clock)
12 Execution timed out 5 ms 17496 KB Time limit exceeded (wall clock)
13 Execution timed out 6 ms 17240 KB Time limit exceeded (wall clock)
14 Execution timed out 10 ms 17620 KB Time limit exceeded (wall clock)
15 Execution timed out 8 ms 18008 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 12 ms 19108 KB Time limit exceeded (wall clock)
2 Execution timed out 16 ms 18492 KB Time limit exceeded (wall clock)
3 Execution timed out 20 ms 19836 KB Time limit exceeded (wall clock)
4 Execution timed out 7 ms 17496 KB Time limit exceeded (wall clock)
5 Execution timed out 8 ms 18008 KB Time limit exceeded (wall clock)
6 Execution timed out 10 ms 18008 KB Time limit exceeded (wall clock)
7 Execution timed out 12 ms 18556 KB Time limit exceeded (wall clock)
8 Execution timed out 22 ms 19888 KB Time limit exceeded (wall clock)
9 Execution timed out 34 ms 21568 KB Time limit exceeded (wall clock)
10 Execution timed out 32 ms 22784 KB Time limit exceeded (wall clock)
11 Execution timed out 35 ms 20940 KB Time limit exceeded (wall clock)
12 Execution timed out 34 ms 23248 KB Time limit exceeded (wall clock)
13 Execution timed out 38 ms 22860 KB Time limit exceeded (wall clock)
14 Execution timed out 34 ms 22584 KB Time limit exceeded (wall clock)
15 Execution timed out 40 ms 23624 KB Time limit exceeded (wall clock)
16 Execution timed out 37 ms 23548 KB Time limit exceeded (wall clock)
17 Execution timed out 43 ms 23556 KB Time limit exceeded (wall clock)