Submission #1195818

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195818		nikulid	Werewolf (IOI18_werewolf)	C++20	15 / 100	4091 ms	31264 KiB

werewolf

#include "werewolf.h"

using namespace std;

/*
  
  Lemma:
  This problem is hard. I will try dfs for subtask 1 and 2, which is 15/100
[working]

*/


vector<int> A;
vector<int> RH, RW;
vector<vector<int>> adj;

void dfs(int node, bool mode, int lim, int i){
  if(!mode){
    // human form (0)
    
    for(auto v:adj[node]){
      if(RH[v] == i)continue; // if we've already been here..
        if(v >= lim){
          RH[v] = i;
          dfs(v, mode, lim, i);
      }
    }

  } else{
    // werewolf form (1)
    
    if(A[i])return;
    if(RH[node]==i){
      A[i]=1;
      return;
    }
    for(auto v:adj[node]){
      if(RW[v] == i)continue; // if we've already been here..
        if(v <= lim){
          RW[v] = i;
          dfs(v, mode, lim, i);
      }
    }

  }
}

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();
    int M = X.size();
    
    A = vector<int>(Q, 0); // answer

    // --- init stuff ---

    // setting up the adjacency matrix
    adj = vector<vector<int>>(N);
    int u,v;
    for(int i=0; i<M; i++){
      u = X[i];
      v = Y[i];
      // u,v are the nodes that are connected..
      adj[u].push_back(v);
      adj[v].push_back(u);      
    }

    // --- ### --- 

    RH = vector<int>(N, -1);
    RW = vector<int>(N, -1);
    for (int i = 0; i < Q; ++i) {
        // first, do dfs on the human paths
        RH[S[i]] = i;
        dfs(S[i], 0, L[i], i);
        // at the end of this process, we have filled the vector RH, such that the cities which are reachable via human form have value `i` specifically. 

        A[i]=0;
        // now, do dfs on the werewolf paths, and check to see if we reach any human paths. This can be checked with (? RH[node]==i)
        RW[E[i]] = i;
        A[i]=0;
        dfs(E[i], 1, R[i], i);
        // ..
    }
    return A;
}

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