Submission #291660

#	Time	Username	Problem	Language	Result	Execution time	Memory
291660		SamAnd	Werewolf (IOI18_werewolf)	C++17	15 / 100	4066 ms	41984 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
typedef long long ll;
const int N = 400005;

int n, m, qq;
vector<int> g[N];

void dfs(int x, int ul, int ur, vector<bool>& c)
{
    if (!(ul <= x && x <= ur))
        return;
    if (c[x])
        return;
    c[x] = true;
    for (int i = 0; i < g[x].size(); ++i)
    {
        int h = g[x][i];
        dfs(h, ul, ur, c);
    }
}

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)
{
    n = N_;
    m = sz(X);
    qq = sz(S);
    for (int i = 0; i < m; ++i)
    {
        int x = X[i];
        int y = Y[i];
        g[x].push_back(y);
        g[y].push_back(x);
    }

    vector<int> ans;
    for (int i = 0; i < qq; ++i)
    {
        vector<bool> cs, ce;
        cs.assign(n, false);
        ce.assign(n, false);
        dfs(S[i], L[i], n - 1, cs);
        dfs(E[i], 0, R[i], ce);
        for (int x = L[i]; x <= R[i]; ++x)
        {
            if (cs[x] && ce[x])
            {
                ans.push_back(1);
                break;
            }
        }
        if (sz(ans) != (i + 1))
            ans.push_back(0);
    }
    return ans;
}

Compilation message (stderr)

werewolf.cpp: In function 'void dfs(int, int, int, std::vector<bool>&)':
werewolf.cpp:22:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for (int i = 0; i < g[x].size(); ++i)
      |                     ~~^~~~~~~~~~~~~

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