oj.uz

답안 #445999

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
445999 2021-07-20T11:47:57 Z cs71107 늑대인간 (IOI18_werewolf) C++14
100 / 100
 914 ms 171812 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;

typedef long long int ll;
typedef pair<int,int> pii;
const int MAXN = 4e5+10;

vector<int> eL[MAXN];
vector<int> eR[MAXN];

vector<pii> queryL[MAXN];
vector<pii> queryR[MAXN];

vector<int> add[MAXN];
vector<pii> query[MAXN];
vector<int> qid[MAXN];

vector<vector<int> > graphL;
vector<vector<int> > graphR;

int Lv[MAXN];
int Rv[MAXN];

int par[MAXN];
int id[MAXN];

int inL[MAXN];
int outL[MAXN];

int inR[MAXN];
int outR[MAXN];

int cal[MAXN];
int tree[MAXN*4];

int seq;

int root(int x){
    if(par[x]==x)return x;
    return par[x] = root(par[x]);
}

void dfsL(int here){

    inL[here] = seq;
    seq++;

    for(int i=0;i<(int)graphL[here].size();i++){
        dfsL(graphL[here][i]);
    }

    outL[here] = seq-1;

    return;
}

void dfsR(int here){

    inR[here] = seq;
    seq++;

    for(int i=0;i<(int)graphR[here].size();i++){
        dfsR(graphR[here][i]);
    }

    outR[here] = seq-1;

    return;
}

inline void update(int tmp){

    while(tmp){
        tree[tmp]++;
        tmp>>=1;
    }
}

inline int getans(int L,int R){

    int res = 0;

    while(L<=R){
        if(L&1){
            res += tree[L];
            L++;
        }
        if(!(R&1)){
            res += tree[R];
            R--;
        }
        L>>=1; R>>=1;
    }

    return res;
}

std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {
  int M = (int)X.size();
  int Q = (int)L.size();

  int x,y;

  for(int i=0;i<M;i++){

    x = X[i];
    y = Y[i];

    if(x>y)swap(x,y);

    eR[x].push_back(y);
    eL[y].push_back(x);

  }

  for(int i=0;i<Q;i++){

    queryL[R[i]].push_back(pii(E[i],i));
    queryR[L[i]].push_back(pii(S[i],i));

  }

  int NN = (N<<1);

  graphL = vector<vector<int> > (NN);
  graphR = vector<vector<int> > (NN);

  int num = N-1;

  for(int i=0;i<N;i++){
    par[i] = i;
    id[i] = i;
  }

  int cur,idx;
  int curid;

  for(int i=0;i<N;i++){

    for(int j=0;j<(int)eL[i].size();j++){
      curid = root(eL[i][j]);

      if(curid^i){
        par[curid] = i;
        num++;
        graphL[num].push_back(id[i]);
        graphL[num].push_back(id[curid]);
        id[i] = num;
      }
    }

    for(int j=0;j<(int)queryL[i].size();j++){
      
      cur = queryL[i][j].f;
      idx = queryL[i][j].s;

      cur = root(cur);

      Lv[idx] = id[cur];
    }
  }

  num = N-1;

  for(int i=0;i<N;i++){
    par[i] = i;
    id[i] = i;
  }

  for(int i=N-1;i>=0;i--){

    for(int j=0;j<(int)eR[i].size();j++){
      curid = root(eR[i][j]);

      if(curid^i){
          par[curid] = i;
          num++;
          graphR[num].push_back(id[i]);
          graphR[num].push_back(id[curid]);
          id[i] = num;
      }
    }

    for(int j=0;j<(int)queryR[i].size();j++){
        cur = queryR[i][j].f;
        idx = queryR[i][j].s;

        cur = root(cur);

        Rv[idx] = id[cur];
    }
  }

  /*
  for(int i=N;i<=((N-1)<<1);i++){
    for(int j=0;j<(int)graphL[i].size();j++){
      cout<<graphL[i][j]<<" ";
    }
    cout<<"\n";
  }

  cout<<"\n";

  for(int i=N;i<=((N-1)<<1);i++){
    for(int j=0;j<(int)graphR[i].size();j++){
      cout<<graphR[i][j]<<" ";
    }
    cout<<"\n";
  }

  cout<<"\n";*/

  /*
  for(int i=0;i<Q;i++){
    cout<<Lv[i]<<" "<<Rv[i]<<"\n";
  }*/

  seq = 0;
  dfsL(((N-1)<<1));

  seq = 0;
  dfsR(((N-1)<<1));

  int la,ra,lb,rb;

  for(int i=0;i<Q;i++){

      la = inL[Lv[i]];
      ra = outL[Lv[i]];

      lb = inR[Rv[i]];
      rb = outR[Rv[i]];

      if(la){
          query[la-1].push_back(pii(lb,rb));
          qid[la-1].push_back((i<<1));
      }
      query[ra].push_back(pii(lb,rb));
      qid[ra].push_back((i<<1)|1);
  }

  for(int i=0;i<N;i++){
      add[inL[i]].push_back(inR[i]);
  }

  int base = 1;

  for(;base<NN;base<<=1);

  int sz = 0;

  for(int i=0;i<NN;i++){

      sz = (int)add[i].size();

      for(int j=0;j<sz;j++){
          update(base+add[i][j]);
      }

      sz = (int)query[i].size();

      for(int j=0;j<sz;j++){

          idx = qid[i][j];
          cur = getans(base+query[i][j].f,base+query[i][j].s);


          if(idx&1){
              cal[(idx>>1)]+=cur;
          }
          else {
              cal[(idx>>1)]-=cur;
          }
      }

  }

  vector<int> ans;

  ans = vector<int> (Q);

  for(int i=0;i<Q;i++){
      if(cal[i])ans[i] = 1;
  }

  return ans;
}

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 66124 KB Output is correct
2 Correct 35 ms 66116 KB Output is correct
3 Correct 36 ms 66092 KB Output is correct
4 Correct 34 ms 66056 KB Output is correct
5 Correct 35 ms 66060 KB Output is correct
6 Correct 37 ms 66116 KB Output is correct
7 Correct 37 ms 66164 KB Output is correct
8 Correct 36 ms 66060 KB Output is correct
9 Correct 36 ms 66124 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 66124 KB Output is correct
2 Correct 35 ms 66116 KB Output is correct
3 Correct 36 ms 66092 KB Output is correct
4 Correct 34 ms 66056 KB Output is correct
5 Correct 35 ms 66060 KB Output is correct
6 Correct 37 ms 66116 KB Output is correct
7 Correct 37 ms 66164 KB Output is correct
8 Correct 36 ms 66060 KB Output is correct
9 Correct 36 ms 66124 KB Output is correct
10 Correct 50 ms 67604 KB Output is correct
11 Correct 43 ms 67496 KB Output is correct
12 Correct 42 ms 67444 KB Output is correct
13 Correct 40 ms 67656 KB Output is correct
14 Correct 42 ms 67600 KB Output is correct
15 Correct 43 ms 67524 KB Output is correct

Subtask #3
34.0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 859 ms 161620 KB Output is correct
2 Correct 742 ms 164680 KB Output is correct
3 Correct 718 ms 160480 KB Output is correct
4 Correct 668 ms 159072 KB Output is correct
5 Correct 711 ms 159344 KB Output is correct
6 Correct 769 ms 160472 KB Output is correct
7 Correct 699 ms 156592 KB Output is correct
8 Correct 720 ms 164824 KB Output is correct
9 Correct 651 ms 159400 KB Output is correct
10 Correct 594 ms 155952 KB Output is correct
11 Correct 601 ms 157436 KB Output is correct
12 Correct 651 ms 157464 KB Output is correct
13 Correct 752 ms 168892 KB Output is correct
14 Correct 706 ms 168872 KB Output is correct
15 Correct 775 ms 168956 KB Output is correct
16 Correct 710 ms 169004 KB Output is correct
17 Correct 678 ms 156444 KB Output is correct

Subtask #4
51.0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 66124 KB Output is correct
2 Correct 35 ms 66116 KB Output is correct
3 Correct 36 ms 66092 KB Output is correct
4 Correct 34 ms 66056 KB Output is correct
5 Correct 35 ms 66060 KB Output is correct
6 Correct 37 ms 66116 KB Output is correct
7 Correct 37 ms 66164 KB Output is correct
8 Correct 36 ms 66060 KB Output is correct
9 Correct 36 ms 66124 KB Output is correct
10 Correct 50 ms 67604 KB Output is correct
11 Correct 43 ms 67496 KB Output is correct
12 Correct 42 ms 67444 KB Output is correct
13 Correct 40 ms 67656 KB Output is correct
14 Correct 42 ms 67600 KB Output is correct
15 Correct 43 ms 67524 KB Output is correct
16 Correct 859 ms 161620 KB Output is correct
17 Correct 742 ms 164680 KB Output is correct
18 Correct 718 ms 160480 KB Output is correct
19 Correct 668 ms 159072 KB Output is correct
20 Correct 711 ms 159344 KB Output is correct
21 Correct 769 ms 160472 KB Output is correct
22 Correct 699 ms 156592 KB Output is correct
23 Correct 720 ms 164824 KB Output is correct
24 Correct 651 ms 159400 KB Output is correct
25 Correct 594 ms 155952 KB Output is correct
26 Correct 601 ms 157436 KB Output is correct
27 Correct 651 ms 157464 KB Output is correct
28 Correct 752 ms 168892 KB Output is correct
29 Correct 706 ms 168872 KB Output is correct
30 Correct 775 ms 168956 KB Output is correct
31 Correct 710 ms 169004 KB Output is correct
32 Correct 678 ms 156444 KB Output is correct
33 Correct 850 ms 162272 KB Output is correct
34 Correct 371 ms 108576 KB Output is correct
35 Correct 859 ms 166072 KB Output is correct
36 Correct 900 ms 162328 KB Output is correct
37 Correct 849 ms 164972 KB Output is correct
38 Correct 846 ms 163224 KB Output is correct
39 Correct 734 ms 171048 KB Output is correct
40 Correct 827 ms 166672 KB Output is correct
41 Correct 750 ms 161196 KB Output is correct
42 Correct 701 ms 157344 KB Output is correct
43 Correct 914 ms 169824 KB Output is correct
44 Correct 810 ms 162752 KB Output is correct
45 Correct 726 ms 171812 KB Output is correct
46 Correct 815 ms 171504 KB Output is correct
47 Correct 791 ms 169212 KB Output is correct
48 Correct 762 ms 168896 KB Output is correct
49 Correct 807 ms 169136 KB Output is correct
50 Correct 749 ms 168996 KB Output is correct
51 Correct 759 ms 164552 KB Output is correct
52 Correct 769 ms 164528 KB Output is correct