제출 #1241412

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1241412		vivkostov	늑대인간 (IOI18_werewolf)	C++20	15 / 100	225 ms	25680 KiB

werewolf

//#pragma once
//#include "grader.cpp"
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
int n,m,q,a[200005],b[200005],l[200005],r[200005],used1[3005],used2[3005],lamp;
vector<int>v[200005],otg;
void dfs1(int beg,int l)
{
    used1[beg]=1;
    int w;
    for(int i=0;i<v[beg].size();i++)
    {
        w=v[beg][i];
        if(w>=l&&!used1[w])dfs1(w,l);
    }
}
void dfs2(int beg,int l,int r)
{
    used2[beg]=1;
    if(used1[beg])
    {
        if(beg>=l&&beg<=r)lamp=1;
    }
    int w;
    for(int i=0;i<v[beg].size();i++)
    {
        w=v[beg][i];
        if(w<=r&&!used2[w])dfs2(w,l,r);
    }
}
vector<int> check_validity(int N,vector<int> X,vector<int> Y,vector<int> S,vector<int> E,vector<int> L, vector<int> R)
{
    n=N;
    m=X.size();
    q=S.size();
    for(int i=1;i<=m;i++)
    {
        v[X[i-1]+1].push_back(Y[i-1]+1);
        v[Y[i-1]+1].push_back(X[i-1]+1);
    }
    for(int i=1;i<=q;i++)
    {
        a[i]=S[i-1]+1;
        b[i]=E[i-1]+1;
        l[i]=L[i-1]+1;
        r[i]=R[i-1]+1;
        memset(used1,0,sizeof(used1));
        memset(used2,0,sizeof(used2));
        lamp=0;
        dfs1(a[i],l[i]);
        dfs2(b[i],l[i],r[i]);
        otg.push_back(lamp);
    }
    return otg;
}

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