Submission #225828

#	Time	Username	Problem	Language	Result	Execution time	Memory
225828		DavidDamian	Werewolf (IOI18_werewolf)	C++11	15 / 100	240 ms	28152 KiB

werewolf

#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
///Subtask 2
///DFS in a 3D graph
vector<int> adjList[6005];
int destiny;
int color[6005];
int c=0;
int n;
int l,r;
int dfsVisit(int u)
{
    if(u==destiny) return 1;
    int ans=0;
    color[u]=c;
    for(int v: adjList[u]){
        if(ans==1) break;
        if(color[v]!=c){
            if(v!=u+n){
                if(v<n && v>=l)
                    ans=dfsVisit(v);
                if(v>=n && v<=r+n)
                    ans=dfsVisit(v);
            }
            if(v==u+n && l<=u && u<=r)
                ans=dfsVisit(v);
        }
    }
    return ans;
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> T, vector<int> L, vector<int> R) {
    int m=X.size();
    int Q=S.size();
    n=N;
    for(int i=0;i<m;i++){
        int a=X[i];
        int b=Y[i];
        adjList[a].push_back(b);
        adjList[b].push_back(a);
        adjList[a+n].push_back(b+n);
        adjList[b+n].push_back(a+n);
    }
    for(int i=0;i<n;i++){
        adjList[i].push_back(i+n);
    }
    vector<int> A;
    for(int i=0;i<Q;i++){
        c++;
        destiny=T[i]+n;
        l=L[i];
        r=R[i];
        A.push_back(dfsVisit(S[i]));
    }
    return A;
}

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