oj.uz

답안 #76410

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
76410 2018-09-13T13:02:12 Z born2rule 늑대인간 (IOI18_werewolf) C++14
15 / 100
 1054 ms 20908 KB 
#include <bits/stdc++.h>
#include "werewolf.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define ll long long
#define db long double
#define ii pair<int,int>
#define vi vector<int>
#define fi first
#define se second
#define sz(a) (int)(a).size()
#define all(a) (a).begin(),(a).end()
#define pb push_back
#define mp make_pair
#define FN(i, n) for (int i = 0; i < (int)(n); ++i)
#define FEN(i,n) for (int i = 1;i <= (int)(n); ++i)
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repv(i,a,b) for(int i=b-1;i>=a;i--)
#define SET(A, val) memset(A, val, sizeof(A))
typedef tree<int ,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set ;
// order_of_key (val): returns the no. of values less than val
// find_by_order (k): returns the kth largest element.(0-based)
#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ','); cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif

const int N=200005;
vi v[N];
bool vis[N];
void dfs(int u,int l,int r,vi &tmp,int type=0)
{
  if(type==0 && u<l) return;
  if(type==1 && u>r) return;
  vis[u]=true;
  tmp.pb(u);
  for(int v1:v[u])
    {
      if(vis[v1]) continue;
      dfs(v1,l,r,tmp,type);
    }
}
vi subtask12(int n,vi S,vi E,vi L,vi R)
{
  int q=sz(S);
  vi ans(q,0);
  rep(i,0,q)
    {
      int x=S[i],y=E[i],l=L[i],r=R[i];
      if(x<l || y>r)
	continue;
      vi tmp1,tmp2;
      rep(j,0,n) vis[j]=false;
      dfs(x,l,r,tmp1);
      rep(j,0,n) vis[j]=false;
      dfs(y,l,r,tmp2,1);
      sort(all(tmp1)); sort(all(tmp2));
      bool ok=false;
      for(int x:tmp1)
	{
	  int ind=lower_bound(all(tmp2),x)-tmp2.begin();
	  if(ind!=sz(tmp2) && tmp2[ind]==x) ok=true;
	}
      if(ok) ans[i]=1;
    }
  return ans;
}
vi check_validity(int n,vi X,vi Y,vi S,vi E,vi L,vi R)
{
  int q=sz(S);
  rep(i,0,sz(X))
    {
      v[X[i]].pb(Y[i]);
      v[Y[i]].pb(X[i]);
    }
  if(n<=3000 && q<=3000)
    return subtask12(n,S,E,L,R);
  return S;
}

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 5112 KB Output is correct
2 Correct 7 ms 5112 KB Output is correct
3 Correct 7 ms 5152 KB Output is correct
4 Correct 6 ms 5152 KB Output is correct
5 Correct 7 ms 5264 KB Output is correct
6 Correct 7 ms 5264 KB Output is correct
7 Correct 7 ms 5264 KB Output is correct
8 Correct 6 ms 5264 KB Output is correct
9 Correct 7 ms 5264 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 5112 KB Output is correct
2 Correct 7 ms 5112 KB Output is correct
3 Correct 7 ms 5152 KB Output is correct
4 Correct 6 ms 5152 KB Output is correct
5 Correct 7 ms 5264 KB Output is correct
6 Correct 7 ms 5264 KB Output is correct
7 Correct 7 ms 5264 KB Output is correct
8 Correct 6 ms 5264 KB Output is correct
9 Correct 7 ms 5264 KB Output is correct
10 Correct 1048 ms 5656 KB Output is correct
11 Correct 662 ms 5656 KB Output is correct
12 Correct 55 ms 5804 KB Output is correct
13 Correct 1054 ms 5804 KB Output is correct
14 Correct 733 ms 5804 KB Output is correct
15 Correct 807 ms 5804 KB Output is correct

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 288 ms 20908 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 5112 KB Output is correct
2 Correct 7 ms 5112 KB Output is correct
3 Correct 7 ms 5152 KB Output is correct
4 Correct 6 ms 5152 KB Output is correct
5 Correct 7 ms 5264 KB Output is correct
6 Correct 7 ms 5264 KB Output is correct
7 Correct 7 ms 5264 KB Output is correct
8 Correct 6 ms 5264 KB Output is correct
9 Correct 7 ms 5264 KB Output is correct
10 Correct 1048 ms 5656 KB Output is correct
11 Correct 662 ms 5656 KB Output is correct
12 Correct 55 ms 5804 KB Output is correct
13 Correct 1054 ms 5804 KB Output is correct
14 Correct 733 ms 5804 KB Output is correct
15 Correct 807 ms 5804 KB Output is correct
16 Incorrect 288 ms 20908 KB Output isn't correct
17 Halted 0 ms 0 KB -