oj.uz

Submission #394134

# Submission time Handle Problem Language Result Execution time Memory
394134 2021-04-25T18:14:14 Z victoriad Regions (IOI09_regions) C++14
2 / 100
 8000 ms 31908 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(vector<vector<int> >&g,int nodo,int bus,vector<bool>&v,int & r,int a,vector<int>&nec){
   v[nodo]=true;
   if(region[nodo]==bus){
     r++;
     for(int i=1;i<nec.size();i++){
       if(nodo>nec[i]){
         r++;
       }
     }
   }
   if(region[nodo]==a){
     nec.push_back(nodo);
   }
   
   for(int c:g[nodo]){
     if(!v[c]){
       dfs(g,c,bus,v,r,a,nec);
     }
   }
 }

int main(){
  int N,R,Q;
  cin>>N>>R>>Q;
  vector<vector<int> >g(N);
  vector<vector<int> >inte(R);
  g.clear();
  region.resize(N);
  int a,b;
  cin>>a;
  a--;
  region[0]=a;
inte[a].push_back(0);
  for(int i=1;i<N;i++){
    cin>>a>>b;
    a--;
    b--;
    region[i]=b;
    g[a].push_back(i);
    inte[b].push_back(i);
  }
   
  for(int i=0;i<Q;i++){
    cin>>a>>b;
    a--;
    b--;
    int con=0;
    vector<bool>v(N,false);
    for(int k=0;k<inte[a].size();k++){
      if(!v[inte[a][k]]){
        vector<int>nec;
        int r=0;
      dfs(g,inte[a][k],b,v,r,a,nec);
      con+=r;
      }
    }
    cout<<con<<"\n";
    }
    
  return 0;
}

Compilation message

regions.cpp: In function 'void dfs(std::vector<std::vector<int> >&, int, int, std::vector<bool>&, int&, int, std::vector<int>&)':
regions.cpp:16:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |      for(int i=1;i<nec.size();i++){
      |                  ~^~~~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:60:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for(int k=0;k<inte[a].size();k++){
      |                 ~^~~~~~~~~~~~~~~

Subtask #1
2.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 200 KB Output isn't correct
2 Incorrect 1 ms 200 KB Output isn't correct
3 Incorrect 3 ms 200 KB Output isn't correct
4 Incorrect 7 ms 200 KB Output isn't correct
5 Incorrect 16 ms 328 KB Output isn't correct
6 Correct 43 ms 328 KB Output is correct
7 Incorrect 44 ms 396 KB Output isn't correct
8 Incorrect 115 ms 328 KB Output isn't correct
9 Correct 431 ms 1096 KB Output is correct
10 Incorrect 614 ms 840 KB Output isn't correct
11 Incorrect 2913 ms 1240 KB Output isn't correct
12 Incorrect 5223 ms 2032 KB Output isn't correct
13 Incorrect 1133 ms 1480 KB Output isn't correct
14 Execution timed out 8032 ms 2112 KB Time limit exceeded
15 Execution timed out 8010 ms 6600 KB Time limit exceeded

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8090 ms 6440 KB Time limit exceeded
2 Execution timed out 8005 ms 4772 KB Time limit exceeded
3 Execution timed out 8090 ms 9400 KB Time limit exceeded
4 Execution timed out 8074 ms 2240 KB Time limit exceeded
5 Execution timed out 8058 ms 5184 KB Time limit exceeded
6 Execution timed out 8029 ms 3952 KB Time limit exceeded
7 Execution timed out 8090 ms 5180 KB Time limit exceeded
8 Execution timed out 8079 ms 13556 KB Time limit exceeded
9 Execution timed out 8038 ms 12072 KB Time limit exceeded
10 Execution timed out 8036 ms 20656 KB Time limit exceeded
11 Execution timed out 8058 ms 11856 KB Time limit exceeded
12 Execution timed out 8053 ms 13356 KB Time limit exceeded
13 Execution timed out 8013 ms 14212 KB Time limit exceeded
14 Execution timed out 8013 ms 13944 KB Time limit exceeded
15 Execution timed out 8029 ms 20800 KB Time limit exceeded
16 Execution timed out 8060 ms 31908 KB Time limit exceeded
17 Execution timed out 8099 ms 29508 KB Time limit exceeded