Submission #591005

#	Time	Username	Problem	Language	Result	Execution time	Memory
591005		PiejanVDC	Werewolf (IOI18_werewolf)	C++17	15 / 100	4058 ms	29816 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) {
    const int m = (int)x.size();
    const int q = (int)s.size();

    vector<int>ans(q, 0);

    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]);
    }

    for(int i = 0 ; i < q ; i++) {
        
        vector<bool>vis(n, 0);
        int S = s[i], E = e[i];
        int L = l[i], R = r[i];

        queue<int>Q;
        Q.push(S);

        vis[S] = 1;

        // check start

        if(S < L) 
            continue;

        while(!Q.empty()) {
            int node = Q.front();
            Q.pop();
            for(auto z : adj[node]) if(!vis[z] && z >= L) {
                vis[z] = 1;
                Q.push(z);
            }
        }

        vector<bool>viss(n, 0);
        viss[E] = 1;

        if(E > R)
            continue;

        Q.push(E);
        while(!Q.empty()) {
            int node = Q.front();
            Q.pop();
            if(vis[node]) {
                ans[i] = 1;
                break;
            }
            for(auto z : adj[node]) if(!viss[z] && z <= R) {
                viss[z] = 1;
                Q.push(z);
            }
        }
    }
    return ans;
}

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