Submission #282029

#	Time	Username	Problem	Language	Result	Execution time	Memory
282029		stoyan_malinin	Werewolf (IOI18_werewolf)	C++14	15 / 100	4019 ms	44316 KiB

werewolf

#include "werewolf.h"
//#include "grader.cpp"

#include <vector>
#include <iostream>
#include <functional>

using namespace std;

const int MAXN = 2e5 + 5;

int n;
vector <int> graph[MAXN];

bool solveDP(int s, int e, int l, int r)
{
    if(s<l || e>r) return false;

    vector <bool> used[2];
    used[0].assign(n+5, false);
    used[1].assign(n+5, false);

    function <void(int, int)> DFS = [&](int x, int state)
    {
        if(used[state][x]==true) return;
        used[state][x] = true;

        //cout << state << " " << x << '\n';

        if(state==0 && x>=l && x<=r) DFS(x, 1);
        for(int y: graph[x])
        {
            if(state==0 && y<l) continue;
            if(state==1 && y>r) continue;

            DFS(y, state);
        }
    };

    DFS(s, 0);
    return used[1][e];
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y,
                                  vector<int> S, vector<int> E,
                                  vector<int> L, vector<int> R)
{
    n = N;
    for(int i = 0;i<X.size();i++)
    {
        graph[ X[i] ].push_back(Y[i]);
        graph[ Y[i] ].push_back(X[i]);
    }

    vector <int> queryAnswers;
    for(int i = 0;i<S.size();i++)
    {
        queryAnswers.push_back(solveDP(S[i], E[i], L[i], R[i]));
    }

    return queryAnswers;
}
/*
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
*/

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

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