제출 #729534

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
729534		t6twotwo	늑대인간 (IOI18_werewolf)	C++17	7 / 100	4048 ms	31476 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
    int M = X.size();
    int Q = S.size();
    vector<vector<int>> adj(N);
    for (int i = 0; i < M; i++) {
        adj[X[i]].push_back(Y[i]);
        adj[Y[i]].push_back(X[i]);
    }
    vector<int> ans(Q);
    for (int i = 0; i < Q; i++) {
        if (S[i] < L[i] || R[i] < E[i]) {
            continue;
        }
        vector<int> hi(N, -1);
        priority_queue<pair<int, int>> p;
        p.emplace(S[i], S[i]);
        while (!p.empty()) {
            auto [v, x] = p.top();
            p.pop();
            if (hi[x] != -1) {
                continue;
            }
            hi[x] = v;
            for (int y : adj[x]) {
                p.emplace(min(v, y), y);
            }
        }
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
        for (int j = L[i]; j <= R[i]; j++) {
            if (hi[j] >= L[i]) {
                q.emplace(j, j);
            }
        }
        vector<int> lo(N, N);
        while (!q.empty()) {
            auto [v, x] = q.top();
            q.pop();
            if (lo[x] != N) {
                continue;
            }
            lo[x] = v;
            for (int y : adj[x]) {
                q.emplace(max(v, y), y);
            }
        }
        if (lo[E[i]] <= R[i]) {
            ans[i] = 1;
        }
    }
    return ans;
}

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