oj.uz

Submission #895343

# Submission time Handle Problem Language Result Execution time Memory
895343 2023-12-29T19:14:10 Z Ahmed57 Regions (IOI09_regions) C++17
0 / 100
 49 ms 23816 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;
        lo.push_back({a,b});
        if(1){
            qu[b].push_back({a,i});
            ans[i] = 0;
        }else{
            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";
    }
    return 0;
}

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 3 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 3 ms 16728 KB Time limit exceeded (wall clock)
7 Execution timed out 4 ms 16912 KB Time limit exceeded (wall clock)
8 Execution timed out 4 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 7 ms 17496 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 14 ms 18880 KB Time limit exceeded (wall clock)
2 Execution timed out 19 ms 18324 KB Time limit exceeded (wall clock)
3 Execution timed out 14 ms 19544 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 19032 KB Time limit exceeded (wall clock)
8 Execution timed out 17 ms 20148 KB Time limit exceeded (wall clock)
9 Execution timed out 34 ms 21376 KB Time limit exceeded (wall clock)
10 Execution timed out 28 ms 22664 KB Time limit exceeded (wall clock)
11 Execution timed out 49 ms 20964 KB Time limit exceeded (wall clock)
12 Execution timed out 35 ms 23156 KB Time limit exceeded (wall clock)
13 Execution timed out 31 ms 22836 KB Time limit exceeded (wall clock)
14 Execution timed out 33 ms 22448 KB Time limit exceeded (wall clock)
15 Execution timed out 36 ms 23464 KB Time limit exceeded (wall clock)
16 Execution timed out 34 ms 23816 KB Time limit exceeded (wall clock)
17 Execution timed out 39 ms 23468 KB Time limit exceeded (wall clock)