oj.uz

Submission #895334

# Submission time Handle Problem Language Result Execution time Memory
895334 2023-12-29T18:59:24 Z Ahmed57 Regions (IOI09_regions) C++17
0 / 100
 46 ms 22408 KB 
#include <bits/stdc++.h>
 
using namespace std;
int frq[25001],a3[25001],xd[25001],ans[25001],x,p,lol[200001],j,a,b,B = 500;
map<pair<int,int>,int> mp;
vector<int> adj[200001];
vector<pair<int,int>> lo,qu[25001];
set<int> qu2[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:12: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]
   12 |     for(j = 0;j<qu[lol[i]].size();j++){
      |               ~^~~~~~~~~~~~~~~~~~
regions.cpp:19:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     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 14936 KB Time limit exceeded (wall clock)
2 Execution timed out 3 ms 14936 KB Time limit exceeded (wall clock)
3 Execution timed out 3 ms 14936 KB Time limit exceeded (wall clock)
4 Execution timed out 3 ms 14936 KB Time limit exceeded (wall clock)
5 Execution timed out 3 ms 14936 KB Time limit exceeded (wall clock)
6 Execution timed out 3 ms 14936 KB Time limit exceeded (wall clock)
7 Execution timed out 3 ms 14936 KB Time limit exceeded (wall clock)
8 Execution timed out 3 ms 15192 KB Time limit exceeded (wall clock)
9 Execution timed out 3 ms 15192 KB Time limit exceeded (wall clock)
10 Execution timed out 4 ms 15448 KB Time limit exceeded (wall clock)
11 Execution timed out 5 ms 15448 KB Time limit exceeded (wall clock)
12 Execution timed out 5 ms 15704 KB Time limit exceeded (wall clock)
13 Execution timed out 9 ms 15508 KB Time limit exceeded (wall clock)
14 Execution timed out 7 ms 16212 KB Time limit exceeded (wall clock)
15 Execution timed out 10 ms 16556 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 14 ms 17508 KB Time limit exceeded (wall clock)
2 Execution timed out 13 ms 16984 KB Time limit exceeded (wall clock)
3 Execution timed out 22 ms 18112 KB Time limit exceeded (wall clock)
4 Execution timed out 7 ms 15960 KB Time limit exceeded (wall clock)
5 Execution timed out 8 ms 16460 KB Time limit exceeded (wall clock)
6 Execution timed out 10 ms 16472 KB Time limit exceeded (wall clock)
7 Execution timed out 15 ms 17240 KB Time limit exceeded (wall clock)
8 Execution timed out 20 ms 18848 KB Time limit exceeded (wall clock)
9 Execution timed out 25 ms 20304 KB Time limit exceeded (wall clock)
10 Execution timed out 36 ms 21348 KB Time limit exceeded (wall clock)
11 Execution timed out 39 ms 19628 KB Time limit exceeded (wall clock)
12 Execution timed out 31 ms 21928 KB Time limit exceeded (wall clock)
13 Execution timed out 31 ms 21456 KB Time limit exceeded (wall clock)
14 Execution timed out 42 ms 20964 KB Time limit exceeded (wall clock)
15 Execution timed out 46 ms 22104 KB Time limit exceeded (wall clock)
16 Execution timed out 34 ms 22164 KB Time limit exceeded (wall clock)
17 Execution timed out 33 ms 22408 KB Time limit exceeded (wall clock)