oj.uz

Submission #933368

# Submission time Handle Problem Language Result Execution time Memory
933368 2024-02-25T15:04:46 Z NourWael Regions (IOI09_regions) C++17
30 / 100
 749 ms 38460 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std; 
int const mxN = 2e5+5;
int  const mxR = 505;
vector<int> adj [mxN];
int in[mxN], out[mxN], t, r , n, region[mxN], q;
vector<pair<int,int>> reg [mxR];
int ans [mxR][mxR], cnt[mxR];

void dfs ( int i, int p ) {

     for(int j=1; j<=r; j++) {
      if(region[i]==j) continue;
      ans[j][region[i]] += cnt[j];
     }
     cnt[region[i]]++;
     for(auto it:adj[i]){
      if(it==p) continue;
      dfs(it,i);
     }
     cnt[region[i]]--;
}
signed main() {
   
   ios_base:: sync_with_stdio(0);
   cin.tie(NULL);
   cout.tie(NULL);

   cin>>n>>r>>q>>region[1];
   for(int i=2; i<=n; i++) {
      int k, h; cin>>k>>h;
      adj[i].push_back(k), adj[k].push_back(i);
      region[i] = h;
   }

   dfs(1,0);

   for(int i=0; i<q; i++) {
      int x,y; cin>>x>>y;
      cout<<ans[x][y]<<endl;
   }
  return 0;

}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9560 KB Output is correct
2 Correct 2 ms 9560 KB Output is correct
3 Correct 3 ms 9560 KB Output is correct
4 Correct 4 ms 9560 KB Output is correct
5 Correct 5 ms 9816 KB Output is correct
6 Correct 11 ms 9816 KB Output is correct
7 Correct 15 ms 9816 KB Output is correct
8 Correct 17 ms 9816 KB Output is correct
9 Correct 29 ms 10328 KB Output is correct
10 Correct 54 ms 10072 KB Output is correct
11 Correct 50 ms 10320 KB Output is correct
12 Correct 69 ms 10584 KB Output is correct
13 Correct 73 ms 10680 KB Output is correct
14 Correct 77 ms 10612 KB Output is correct
15 Correct 100 ms 13712 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 447 ms 12928 KB Output is correct
2 Correct 517 ms 12824 KB Output is correct
3 Correct 749 ms 14712 KB Output is correct
4 Runtime error 18 ms 25548 KB Execution killed with signal 11
5 Runtime error 18 ms 25996 KB Execution killed with signal 11
6 Runtime error 23 ms 27232 KB Execution killed with signal 11
7 Runtime error 24 ms 28288 KB Execution killed with signal 11
8 Runtime error 32 ms 29684 KB Execution killed with signal 11
9 Runtime error 42 ms 33232 KB Execution killed with signal 11
10 Runtime error 48 ms 34120 KB Execution killed with signal 11
11 Runtime error 61 ms 38460 KB Execution killed with signal 11
12 Runtime error 50 ms 35604 KB Execution killed with signal 11
13 Runtime error 50 ms 36044 KB Execution killed with signal 11
14 Runtime error 57 ms 36856 KB Execution killed with signal 11
15 Runtime error 53 ms 36120 KB Execution killed with signal 11
16 Runtime error 52 ms 36144 KB Execution killed with signal 11
17 Runtime error 58 ms 35920 KB Execution killed with signal 11