Submission #90623

#	Time	Username	Problem	Language	Result	Execution time	Memory
90623		Retro3014	Werewolf (IOI18_werewolf)	C++17	15 / 100	314 ms	34248 KiB

werewolf

#include "werewolf.h"
#include <vector>
#include <algorithm>

using namespace std;
#define MAX_N 200000

int n, m, q;
vector<int> graph[MAX_N+1], s, e, l, r;

vector<int> solve1();

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=(int)X.size(); q=(int)S.size();
    for(int i=0; i<m; i++){
        graph[X[i]].push_back(Y[i]);
        graph[Y[i]].push_back(X[i]);
    }
    for(int i=0; i<q; i++){
        s.push_back(S[i]);
        e.push_back(E[i]);
        l.push_back(L[i]);
        r.push_back(R[i]);
    }
    if(n<=3000 && m<=6000 && q<=3000){
        return solve1();
    }
    return s;
}

int visited[MAX_N+1];

void dfs1(int x, int y){
    if(visited[x]>0){
        return;
    }
    if(x<y){
        return;
    }
    visited[x]++;
    for(int i=0; i<graph[x].size(); i++){
        dfs1(graph[x][i], y);
    }
}

void dfs2(int x, int y){
    if(visited[x]>=2){
        return;
    }
    if(x>y){
        return;
    }
    visited[x]+=2;
    for(int i=0; i<graph[x].size(); i++){
        dfs2(graph[x][i], y);
    }
}

vector<int> solve1(){
    vector<int> ans(q);
    for(int t=0; t<q; t++){
        dfs1(s[t], l[t]);
        dfs2(e[t], r[t]);
        for(int i=0; i<n; i++){
            if(visited[i]==3){
                ans[t]=1;
            }
            visited[i]=0;
        }
    }
    return ans;
}

Compilation message (stderr)

werewolf.cpp: In function 'void dfs1(int, int)':
werewolf.cpp:41:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<graph[x].size(); i++){
                  ~^~~~~~~~~~~~~~~~
werewolf.cpp: In function 'void dfs2(int, int)':
werewolf.cpp:54:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<graph[x].size(); i++){
                  ~^~~~~~~~~~~~~~~~

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