Submission #295560

#	Time	Username	Problem	Language	Result	Execution time	Memory
295560		eohomegrownapps	Werewolf (IOI18_werewolf)	C++14	15 / 100	4062 ms	22264 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;

int n,q;
vector<vector<int>> adjlist;

vector<int> cnt;
int maxcnt = 0;

void bfs(int start, int l, int r, bool human){
    queue<int> q;
    vector<bool> visited(n);
    visited[start]=true;
    cnt[start]++;
    maxcnt=max(maxcnt,cnt[start]);
    q.push(start);
    while (q.size()>0){
        int f = q.front();
        q.pop();
        for (int i : adjlist[f]){
            if (visited[i]){continue;}
            if ((human&&i<l)||((!human)&&i>r)){continue;}
            cnt[i]++;
            maxcnt=max(maxcnt,cnt[i]);
            visited[i]=true;
            q.push(i);
        }
    }
}

std::vector<int> check_validity(int N, std::vector<int> x, std::vector<int> y,
                                std::vector<int> s, std::vector<int> e,
                                std::vector<int> L, std::vector<int> R) {
    q = s.size();
    n=N;
    
    adjlist.resize(n);
    for (int i = 0; i<x.size(); i++){
        //cout<<x[i]<<' '<<y[i]<<endl;
        adjlist[x[i]].push_back(y[i]);
        adjlist[y[i]].push_back(x[i]);
    }

    vector<int> ans(q,0);

    for (int i = 0; i<q; i++){
        cnt.assign(n,0);
        maxcnt=0;
        bfs(s[i],L[i],R[i],true);
        bfs(e[i],L[i],R[i],false);
        if (maxcnt==2){
            ans[i]=1;
        }
    }
    return ans;
}

Compilation message (stderr)

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:39:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for (int i = 0; i<x.size(); i++){
      |                     ~^~~~~~~~~

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