Submission #1189940

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189940		MatteoArcari	Werewolf (IOI18_werewolf)	C++20	15 / 100	4094 ms	21436 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;

vi check_validity(int n, vi x, vi y, vi s, vi e, vi l, vi r) {
    int q = s.size();
    int m = x.size();
    vector<vi> adj(n);
    for (int i = 0; i < m; i++) {
        adj[x[i]].push_back(y[i]);
        adj[y[i]].push_back(x[i]);
    }

    vi ans(q);

    for (int i = 0; i < q; i++) {
        vector<bool> visL(n), visR(n);
        queue<int> qu;
        qu.push(s[i]); visL[s[i]] = 1; 
        while (!qu.empty()) {
            int j = qu.front();
            qu.pop();
            for (int k: adj[j]) {
                if (k < l[i]) continue;
                if (visL[k]) continue;
                visL[k] = 1;
                qu.push(k); 
            }
        }
        qu.push(e[i]); visR[e[i]] = 1; 
        while (!qu.empty()) {
            int j = qu.front();
            qu.pop();
            for (int k: adj[j]) {
                if (k > r[i]) continue;
                if (visR[k]) continue;
                visR[k] = 1;
                qu.push(k); 
            }
        }
        for (int j = l[i]; j <= r[i]; j++) {
            if (visL[j] && visR[j]) {
                ans[i] = 1;
                break;
            }
        }
    }

    return ans;
}

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