Submission #1195856

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195856		clementine	늑대인간 (IOI18_werewolf)	C++20	15 / 100	4094 ms	26136 KiB

werewolf

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

vector<int> graph[200005];
bool visited[200005];
bool hvisited[200005];
bool result = false;

void humanspan(int u, int l)
{
    hvisited[u] = true;
    //cout << "hu " << u << '\n';
    for(auto v: graph[u])
    {
        if(!hvisited[v] && v >= l)
        {
            humanspan(v, l);
        }
    }
}

void wolfspan(int u, int l, int r)
{
    visited[u] = true;
    //cout << "wu " << u << '\n';
    for(auto v: graph[u])
    {
        if(!visited[v] && v <=r)
        {
            wolfspan(v, l, r);
        }
    }
}
int solve(int n, int s, int e, int l, int r)
{
    result = false;
    for(int i = 0; i < n; i ++)
    {
        visited[i] = false;
        hvisited[i] = false;
    }
    humanspan(s, l);
    wolfspan(e, l, r);
    for(int i = l; i <=r; i ++)
    {
        if(visited[i]  && hvisited[i])
        {
            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) 
{
    int Q = S.size();
    vector<int> A(Q, 0);
    for(int i = 0; i < X.size(); i ++)
    {
        graph[X[i]].push_back(Y[i]);
        graph[Y[i]].push_back(X[i]);
    }
    for(int i = 0; i < Q; i ++)
    {
        A[i] = solve(N, S[i], E[i], L[i], R[i]);
    }
    return A;
}

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