Submission #738119

#	Time	Username	Problem	Language	Result	Execution time	Memory
738119		danikoynov	Werewolf (IOI18_werewolf)	C++14	15 / 100	4046 ms	42416 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>

using namespace std;

const int maxn = 4e5 + 10;

struct query
{
    int l, r, s, e;

    query(int _l = 0, int _r = 0, int _s = 0, int _e = 0)
    {
        l = _l;
        r = _r;
        s = _s;
        e = _e;
    }
}ask[maxn];

int n, q, m, used0[maxn], used1[maxn];
vector < int > graph[maxn];

void bfs0(int v, int l)
{
    if (v < l)
        return;

    used0[v] = 1;
    queue < int > q;
    q.push(v);
    while(!q.empty())
    {
        int cur = q.front();
        q.pop();
        for (int u : graph[cur])
        {
            if (u < l)
                continue;
            if (used0[u] == 0)
            {
                q.push(u);
                used0[u] = 1;
            }
        }
    }
}

void bfs1(int v, int r)
{
    if (v > r)
        return;

    used1[v] = 1;
    queue < int > q;
    q.push(v);
    while(!q.empty())
    {
        int cur = q.front();
        q.pop();
        for (int u : graph[cur])
        {
            if (u > r)
                continue;
            if (used1[u] == 0)
            {
                q.push(u);
                used1[u] = 1;
            }
        }
    }
}


int solve_query(query cur)
{
    for (int i = 0; i < n; i ++)
    {
        used0[i] = used1[i] = 0;
    }

    bfs0(cur.s, cur.l);
    bfs1(cur.e, cur.r);

    for (int i = 0; i < n; i ++)
    {
        if (used0[i] == 1 && used1[i] == 1)
            return 1;
    }
    return 0;
}
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;
    q = L.size();
    m = X.size();
    for (int i = 0; i < q; i ++)
    {
        ask[i] = query(L[i], R[i], S[i], E[i]);
    }
    for (int i = 0; i < m; i ++)
    {
        graph[X[i]].push_back(Y[i]);
        graph[Y[i]].push_back(X[i]);
    }

    vector < int > ans(q, 0);
    for (int i = 0; i < q; i ++)
    {
        ans[i] = solve_query(ask[i]);
    }
    return ans;
}

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