Submission #1210279

#TimeUsernameProblemLanguageResultExecution timeMemory
1210279repsakWerewolf (IOI18_werewolf)C++20
0 / 100
4091 ms22160 KiB
#include "werewolf.h" #include <bits/stdc++.h> using namespace std; 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); vector<vector<int>> adj(N); for(int i = 0; i < X.size(); i++){ adj[X[i]].push_back(Y[i]); adj[Y[i]].push_back(X[i]); } for(int i = 0; i < Q; i++){ int low = L[i]; int high = R[i]; int start = S[i]; int end = E[i]; queue<vector<int>> q; q.push({start, start <= high}); //u, transform state: 0 = human, 1 = can be both, 2 = wolf: Impossible to go back from 2 vector<int> visited(N); int isPossible = 0; while(!q.empty()){ int u = q.front()[0]; int state = q.front()[1]; q.pop(); if(u == end && (state == 2 || state == 1)){ isPossible = 1; break; } if(visited[u]) continue; visited[u] = 1; for(auto v : adj[u]){ if(v > high){ if(state == 2) continue; if(v == end) continue; q.push({v, 0}); }else if(v < low){ if(state == 0) continue; q.push({v, 2}); }else{ q.push({v, 1}); } } } A[i] = isPossible; } return A; } // 6 6 3 // 5 1 1 2 1 3 3 4 3 0 5 2 // 4 2 1 2 4 2 2 2 5 4 3 4 // #include "grader.cpp"
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...