oj.uz

Submission #417940

# Submission time Handle Problem Language Result Execution time Memory
417940 2021-06-04T15:44:33 Z victoriad Regions (IOI09_regions) C++14
40 / 100
 3791 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,int x,int a){
     vi[nodo]=true;
     b[region[nodo]]+=x;
	 if(region[nodo]==a)x++;
     for(int c:g[nodo]){
         if(!vi[c]){
             dfs(c,g,vi,b,x,a);
         }
     }
 }
 
int main(){
  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;
  for(int i=1;i<N;i++){
    cin>>a>>b;
    a--;
    b--;
    region[i]=b;
    g[a].push_back(i);
  }
  vector<vector<int> >bus(R);
  vector<int>vacio(R,0);
  for(int i=0;i<R;i++)bus[i]=vacio;
 vector<bool>rv(N,false);
  for(int i=0;i<N;i++){
      int j=region[i];
	  if(!rv[j]){
		  rv[j]=true;
      vector<bool>vi(N,false);
      dfs(0,g,vi,bus[j],0,j);
	  }
  }
  for(int i=0;i<Q;i++){
      cin>>a>>b;
        a--;
        b--;
      cout<<bus[a][b]<<"\n";
  }
   
    
  return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 3 ms 200 KB Output is correct
4 Correct 4 ms 200 KB Output is correct
5 Correct 9 ms 328 KB Output is correct
6 Correct 21 ms 584 KB Output is correct
7 Correct 32 ms 456 KB Output is correct
8 Correct 27 ms 580 KB Output is correct
9 Correct 74 ms 1224 KB Output is correct
10 Correct 208 ms 1552 KB Output is correct
11 Correct 228 ms 1480 KB Output is correct
12 Correct 323 ms 2616 KB Output is correct
13 Correct 453 ms 1800 KB Output is correct
14 Correct 384 ms 2088 KB Output is correct
15 Correct 372 ms 6004 KB Output is correct

Subtask #2
25.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 945 ms 6008 KB Output is correct
2 Correct 1474 ms 4408 KB Output is correct
3 Correct 1787 ms 8584 KB Output is correct
4 Correct 3791 ms 64832 KB Output is correct
5 Correct 2232 ms 102464 KB Output is correct
6 Runtime error 95 ms 131076 KB Execution killed with signal 9
7 Runtime error 106 ms 131076 KB Execution killed with signal 9
8 Runtime error 122 ms 131076 KB Execution killed with signal 9
9 Runtime error 156 ms 131076 KB Execution killed with signal 9
10 Runtime error 173 ms 131076 KB Execution killed with signal 9
11 Runtime error 192 ms 131076 KB Execution killed with signal 9
12 Runtime error 182 ms 131076 KB Execution killed with signal 9
13 Runtime error 183 ms 131076 KB Execution killed with signal 9
14 Runtime error 221 ms 131076 KB Execution killed with signal 9
15 Runtime error 217 ms 131076 KB Execution killed with signal 9
16 Runtime error 202 ms 131076 KB Execution killed with signal 9
17 Runtime error 192 ms 131076 KB Execution killed with signal 9