제출 #790979

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
790979		YassirSalama	늑대인간 (IOI18_werewolf)	C++14	0 / 100	98 ms	27916 KiB

werewolf

#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
#define all(v) v.begin(),v.end()
#define OVL(v,s) for(auto x:v) cout<<x<<s;cout<<endl;
#define ll long long
#define pb push_back
const int MAXN=200;
int dp[MAXN][2];
bool visited[MAXN][2];
vector<vector<int>> v(MAXN);
bool dfs(int node,bool ishuman,int l,int r,int dest){
    if(node>r&&!ishuman) return false;
    if(node<l&&ishuman) return false;
    if(node==dest) return dp[node][ishuman]=true;
    if(dp[node][ishuman]!=-1) return dp[node][ishuman];
    if(visited[node][ishuman]) return false;
    visited[node][ishuman]=true;
    //If is human is true then You didn't change yet 
    bool ok=false;
    if(l<=node&&node<=r){
      //Here he is in a node where he can transform
      for(auto x:v[node]){
        ok|=dfs(x,(!ishuman),l,r,dest);
        if(ok) return dp[node][ishuman]=true;
      }
    }
    for(auto x:v[node]) {ok|=dfs(x,ishuman,l,r,dest);if(ok) return dp[node][ishuman]=true;}
    return dp[node][ishuman]=ok;
}

vector<int> check_validity(int n, vector<int> a, vector<int> b,
                                vector<int> ql, vector<int> qr,
                                vector<int> l, vector<int> r) {
  int q = ql.size();
  for(int i=0;i<a.size();i++){
    v[a[i]].pb(b[i]);
    v[b[i]].pb(a[i]);
  }
  vector<int> ans(q,0);
  for(int i=0;i<n;i++){
    memset(dp,-1,sizeof(dp));
    memset(visited,false,sizeof(visited));
    bool ok=false;
    if(l[i]<=ql[i]&&ql[i]<=r[i]) ok|=dfs(ql[i],0,l[i],r[i],qr[i]);
    ok=dfs(ql[i],1,l[i],r[i],qr[i]);
    if(ok) ans[i]=1;
    else ans[i]=0;
  }
  return ans;
}

// namespace {

// int read_int() {
//   int x;
//   if (scanf("%d", &x) != 1) {
//     fprintf(stderr, "Error while reading input\n");
//     exit(1);
//   }
//   return x;
// }

// }  // namespace

// int main() {
//   int N = read_int();
//   int M = read_int();
//   int Q = read_int();
//   std::vector<int> X(M), Y(M), S(Q), E(Q), L(Q), R(Q);
//   for (int j = 0; j < M; ++j) {
//     X[j] = read_int();
//     Y[j] = read_int();
//   }
//   for (int i = 0; i < Q; ++i) {
//     S[i] = read_int();
//     E[i] = read_int();
//     L[i] = read_int();
//     R[i] = read_int();
//   }

//   std::vector<int> A = check_validity(N, X, Y, S, E, L, R);
//   for (size_t i = 0; i < A.size(); ++i) {
//     printf("%d\n", A[i]);
//   }
//   return 0;
// }

컴파일 시 표준 에러 (stderr) 메시지

werewolf.cpp: In function 'bool dfs(int, bool, int, int, int)':
werewolf.cpp:15:44: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   15 |     if(node==dest) return dp[node][ishuman]=true;
      |                           ~~~~~~~~~~~~~~~~~^~~~~
werewolf.cpp:25:40: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   25 |         if(ok) return dp[node][ishuman]=true;
      |                       ~~~~~~~~~~~~~~~~~^~~~~
werewolf.cpp:28:85: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   28 |     for(auto x:v[node]) {ok|=dfs(x,ishuman,l,r,dest);if(ok) return dp[node][ishuman]=true;}
      |                                                                    ~~~~~~~~~~~~~~~~~^~~~~
werewolf.cpp:29:29: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   29 |     return dp[node][ishuman]=ok;
      |            ~~~~~~~~~~~~~~~~~^~~
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:36:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |   for(int i=0;i<a.size();i++){
      |               ~^~~~~~~~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51