oj.uz

Submission #418201

# Submission time Handle Problem Language Result Execution time Memory
418201 2021-06-05T08:10:57 Z victoriad Regions (IOI09_regions) C++14
12 / 100
 8000 ms 26888 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;
 int total;
 void dfs(int nodo,vector<vector<int> >&g,vector<bool>&vi,int b,int x,int a){
     vi[nodo]=true;
     if(region[nodo]==b)total+=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);
  }
  
  for(int i=0;i<Q;i++){
      cin>>a>>b;
        a--;
        b--;
		total=0;
		vector<bool>vi(N,false);
		dfs(0,g,vi,b,0,a);
      cout<<total<<"\n";
  }
   
    
  return 0;
}

Subtask #1
12.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 5 ms 200 KB Output is correct
5 Correct 12 ms 200 KB Output is correct
6 Correct 37 ms 328 KB Output is correct
7 Correct 103 ms 328 KB Output is correct
8 Correct 148 ms 328 KB Output is correct
9 Correct 336 ms 948 KB Output is correct
10 Correct 2051 ms 840 KB Output is correct
11 Correct 3928 ms 1096 KB Output is correct
12 Correct 4035 ms 1736 KB Output is correct
13 Execution timed out 8019 ms 1352 KB Time limit exceeded
14 Execution timed out 8036 ms 1884 KB Time limit exceeded
15 Execution timed out 8016 ms 5704 KB Time limit exceeded

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8019 ms 5696 KB Time limit exceeded
2 Execution timed out 8047 ms 4160 KB Time limit exceeded
3 Execution timed out 8053 ms 8252 KB Time limit exceeded
4 Execution timed out 8034 ms 1852 KB Time limit exceeded
5 Execution timed out 8071 ms 4408 KB Time limit exceeded
6 Execution timed out 8090 ms 3440 KB Time limit exceeded
7 Execution timed out 8016 ms 4328 KB Time limit exceeded
8 Execution timed out 8063 ms 11384 KB Time limit exceeded
9 Execution timed out 8073 ms 10072 KB Time limit exceeded
10 Execution timed out 8029 ms 17176 KB Time limit exceeded
11 Execution timed out 8077 ms 9568 KB Time limit exceeded
12 Execution timed out 8074 ms 11520 KB Time limit exceeded
13 Execution timed out 8031 ms 12312 KB Time limit exceeded
14 Execution timed out 8071 ms 11460 KB Time limit exceeded
15 Execution timed out 8083 ms 17352 KB Time limit exceeded
16 Execution timed out 8076 ms 26888 KB Time limit exceeded
17 Execution timed out 8023 ms 24896 KB Time limit exceeded