oj.uz

Submission #405615

# Submission time Handle Problem Language Result Execution time Memory
405615 2021-05-16T15:12:40 Z victoriad Regions (IOI09_regions) C++14
0 / 100
 8000 ms 131076 KB 
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <utility>
#include <queue>
#include <map>
#include <iomanip>
using namespace std;
 vector<int>region;
 void dfs(int nodo,vector<vector<int> >&g,vector<bool>&vi,vector<int>&b){
     vi[nodo]=true;
     b[region[nodo]]++;
     for(int c:g[nodo]){
         if(!vi[c]){
             dfs(c,g,vi,b);
         }
     }
 }
 
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);

  int N,R,Q;
  cin>>N>>R>>Q;
  vector<vector<int> >g(N);
  g.clear();
  region.resize(N);
  int a,b;
  cin>>a;
  a--;
  region[0]=a;
  vector<vector<int> >bus(R);
  vector<int>vacio(R,0);
  for(int i=0;i<R;i++)bus[i]=vacio;

  for(int i=1;i<N;i++){
    cin>>a>>b;
    a--;
    b--;
    region[i]=b;
    bus[region[0]][b]++;
    g[a].push_back(i);
  }


  for(int i=1;i<N;i++){
      int j=region[i];
      vector<bool>vi(N,false);
      dfs(i,g,vi,bus[j]);
  }
  for(int i=0;i<Q;i++){
      cin>>a>>b;
        a--;
        b--;
      cout<<bus[a][b]<<"\n";
  }
   
    
  return 0;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2 ms 204 KB Time limit exceeded (wall clock)
2 Execution timed out 1 ms 200 KB Time limit exceeded (wall clock)
3 Execution timed out 2 ms 200 KB Time limit exceeded (wall clock)
4 Execution timed out 1 ms 200 KB Time limit exceeded (wall clock)
5 Execution timed out 2 ms 328 KB Time limit exceeded (wall clock)
6 Execution timed out 6 ms 584 KB Time limit exceeded (wall clock)
7 Execution timed out 4 ms 456 KB Time limit exceeded (wall clock)
8 Execution timed out 8 ms 584 KB Time limit exceeded (wall clock)
9 Execution timed out 193 ms 1224 KB Time limit exceeded (wall clock)
10 Execution timed out 36 ms 1480 KB Time limit exceeded (wall clock)
11 Execution timed out 135 ms 1480 KB Time limit exceeded (wall clock)
12 Execution timed out 742 ms 2504 KB Time limit exceeded (wall clock)
13 Execution timed out 37 ms 1736 KB Time limit exceeded (wall clock)
14 Execution timed out 195 ms 2120 KB Time limit exceeded (wall clock)
15 Execution timed out 8031 ms 5324 KB Time limit exceeded

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8020 ms 5616 KB Time limit exceeded
2 Execution timed out 2791 ms 4344 KB Time limit exceeded (wall clock)
3 Execution timed out 8015 ms 8004 KB Time limit exceeded
4 Execution timed out 955 ms 64680 KB Time limit exceeded (wall clock)
5 Execution timed out 6699 ms 102000 KB Time limit exceeded (wall clock)
6 Runtime error 77 ms 131076 KB Execution killed with signal 9
7 Runtime error 63 ms 131076 KB Execution killed with signal 9
8 Runtime error 63 ms 131076 KB Execution killed with signal 9
9 Runtime error 62 ms 131076 KB Execution killed with signal 9
10 Runtime error 65 ms 131076 KB Execution killed with signal 9
11 Runtime error 64 ms 131076 KB Execution killed with signal 9
12 Runtime error 65 ms 131076 KB Execution killed with signal 9
13 Runtime error 69 ms 131076 KB Execution killed with signal 9
14 Runtime error 61 ms 131076 KB Execution killed with signal 9
15 Runtime error 68 ms 131076 KB Execution killed with signal 9
16 Runtime error 68 ms 131076 KB Execution killed with signal 9
17 Runtime error 63 ms 131076 KB Execution killed with signal 9