oj.uz

Submission #741127

# Submission time Handle Problem Language Result Execution time Memory
741127 2023-05-13T15:14:17 Z almothana05 Werewolf (IOI18_werewolf) C++14
15 / 100
 4000 ms 26784 KB 
#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
int vis[2][300000];
vector<int>kinder[300000] , erg;
priority_queue<pair<int ,int> >q;
int bfs(int x , int en , int l , int r){
  if(x >= l){
    q.push({0 , x});
  }
  if(x <= r){
    q.push({-1 , x});
  }
  while(q.size()){
    int jet = q.top().second , cmp = q.top().first;
    q.pop();
    for(int i = 0 ; i < kinder[jet].size() ; i++){
      int kind = kinder[jet][i];
      if(cmp == -1){
        if(kind <= r && vis[1][kind] == 0){
          vis[1][kind] = 1;
          q.push({-1 , kind});
        }
      }
      else{
        if(kind <= r && vis[1][kind] == 0 && (kind >= l || jet <= r)){
          vis[1][kind] = 1;
          q.push({-1 , kind});
        }
        if(kind >= l && vis[0][kind] == 0){
          vis[0][kind] = 1;
          q.push({0 , kind});
        }
      }
      
    }
  }
  return vis[1][en] == 1;
}
vector<int> check_validity(int menge, vector<int> x, vector<int> y,
                                vector<int> s, vector<int> e,
                                vector<int> l, vector<int> r) {
  if(x.size() == menge - 1){

  } 
  for(int i = 0 ; i < x.size() ; i++){
    kinder[x[i]].push_back(y[i]);
    kinder[y[i]].push_back(x[i]);
  }
  for(int i = 0 ; i < s.size() ; i++){
    for(int i = 0 ; i < menge ; i++){
      vis[0][i] = 0;
      vis[1][i] = 0;
    }
    int x = bfs(s[i] , e[i] , l[i] , r[i]);
    erg.push_back(x);
  }                
  return erg;
}

Compilation message

werewolf.cpp: In function 'int bfs(int, int, int, int)':
werewolf.cpp:17:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for(int i = 0 ; i < kinder[jet].size() ; i++){
      |                     ~~^~~~~~~~~~~~~~~~~~~~
werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:43:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   43 |   if(x.size() == menge - 1){
      |      ~~~~~~~~~^~~~~~~~~~~~
werewolf.cpp:46:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |   for(int i = 0 ; i < x.size() ; i++){
      |                   ~~^~~~~~~~~~
werewolf.cpp:50:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |   for(int i = 0 ; i < s.size() ; i++){
      |                   ~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7252 KB Output is correct
2 Correct 5 ms 7356 KB Output is correct
3 Correct 4 ms 7356 KB Output is correct
4 Correct 4 ms 7356 KB Output is correct
5 Correct 6 ms 7352 KB Output is correct
6 Correct 5 ms 7380 KB Output is correct
7 Correct 5 ms 7360 KB Output is correct
8 Correct 5 ms 7252 KB Output is correct
9 Correct 6 ms 7344 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7252 KB Output is correct
2 Correct 5 ms 7356 KB Output is correct
3 Correct 4 ms 7356 KB Output is correct
4 Correct 4 ms 7356 KB Output is correct
5 Correct 6 ms 7352 KB Output is correct
6 Correct 5 ms 7380 KB Output is correct
7 Correct 5 ms 7360 KB Output is correct
8 Correct 5 ms 7252 KB Output is correct
9 Correct 6 ms 7344 KB Output is correct
10 Correct 1126 ms 7776 KB Output is correct
11 Correct 836 ms 7764 KB Output is correct
12 Correct 39 ms 7780 KB Output is correct
13 Correct 809 ms 7768 KB Output is correct
14 Correct 385 ms 7772 KB Output is correct
15 Correct 701 ms 7996 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4035 ms 26784 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7252 KB Output is correct
2 Correct 5 ms 7356 KB Output is correct
3 Correct 4 ms 7356 KB Output is correct
4 Correct 4 ms 7356 KB Output is correct
5 Correct 6 ms 7352 KB Output is correct
6 Correct 5 ms 7380 KB Output is correct
7 Correct 5 ms 7360 KB Output is correct
8 Correct 5 ms 7252 KB Output is correct
9 Correct 6 ms 7344 KB Output is correct
10 Correct 1126 ms 7776 KB Output is correct
11 Correct 836 ms 7764 KB Output is correct
12 Correct 39 ms 7780 KB Output is correct
13 Correct 809 ms 7768 KB Output is correct
14 Correct 385 ms 7772 KB Output is correct
15 Correct 701 ms 7996 KB Output is correct
16 Execution timed out 4035 ms 26784 KB Time limit exceeded
17 Halted 0 ms 0 KB -