제출 #772224

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
772224		I_Love_EliskaM_	늑대인간 (IOI18_werewolf)	C++14	15 / 100	282 ms	13200 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back

vector<int> p1(int n, vector<int>x, vector<int>y, vector<int>s, vector<int>e, vector<int>L, vector<int>R) {
  int m=x.size(), Q=L.size();
  vector<int> ok(n,0), vis(n,0);
  vector<vector<int>> adj(n);
  forn(i,m) {
    int u=x[i], v=y[i];
    adj[u].pb(v); adj[v].pb(u);
  }
  vector<int> ans(Q);
  forn(it,Q) {
    int l=L[it], r=R[it];
    queue<int> q; q.push(s[it]);
    while (q.size()) {
      auto u=q.front(); q.pop();
      if (u<l) continue;
      if (vis[u]) continue;
      vis[u]=1;
      if (l<=u && u<=r) ok[u]=1;
      for(auto&v:adj[u]) q.push(v);
    }
    forn(i,n) vis[i]=0;
    forn(i,n) if (ok[i]) q.push(i);
    while (q.size()) {
      auto u=q.front(); q.pop();
      if (u>r) continue;
      if (vis[u]) continue;
      vis[u]=1;
      for(auto&v:adj[u]) q.push(v);
    }
    ans[it]=vis[e[it]];
    forn(i,n) vis[i]=ok[i]=0;
  }
  return ans;
}

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 m=x.size(), q=l.size();
    if (max(m,q)<=6000) {
        return p1(n,x,y,s,e,l,r);
    }
    return vector<int>(q,0);
}

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