Submission #566367

#	Time	Username	Problem	Language	Result	Execution time	Memory
566367		elazarkoren	Werewolf (IOI18_werewolf)	C++17	15 / 100	4078 ms	40384 KiB

werewolf

#include <bits/stdc++.h>
#include "werewolf.h"
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
typedef vector<bool> vb;

void DfsMax(vvi &graph, int node, int max, vb &visited) {
    visited[node] = true;
    for (int neighbor : graph[node]) {
        if (neighbor <= max && !visited[neighbor]) DfsMax(graph, neighbor, max, visited);
    }
}

void DfsMin(vvi &graph, int node, int min, vb &visited) {
    visited[node] = true;
    for (int neighbor : graph[node]) {
        if (neighbor >= min && !visited[neighbor]) DfsMin(graph, neighbor, min, visited);
    }
}

vi check_validity(int n, vi x, vi y, vi s, vi e, vi l, vi r) {
    int m = x.size();
    vvi graph(n);
    for (int i = 0; i < m; i++) {
        graph[x[i]].push_back(y[i]);
        graph[y[i]].push_back(x[i]);
    }
    int q = s.size();
    vi ans(q);
    for (int i = 0; i < q; i++) {
        vb visited1(n), visited2(n);
        DfsMin(graph, s[i], l[i], visited1);
        DfsMax(graph, e[i], r[i], visited2);
        for (int j = 0; j < n; j++) {
            if (visited1[j] && visited2[j]) {
                ans[i] = 1;
                break;
            }
        }
    }
    return ans;
}
//6 6 3
//0 3
//1 2
//1 5
//1 3
//2 5
//3 4
//
//4 2 1 2
//4 2 2 2
//5 4 3 4

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