oj.uz

답안 #548371

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
548371 2022-04-13T07:30:02 Z cig32 늑대인간 (IOI18_werewolf) C++17
15 / 100
 4000 ms 139472 KB 
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <queue>
#include <iostream>
//#include "werewolf.h"



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);



struct edge {
  int f, t, w;
};
class cmp1 { // MST for wolf
  public:
  bool operator() (edge x, edge y) {
    return x.w > y.w;
  }
};
class cmp2 { // MST for human
  public:
  bool operator() (edge x, edge y) {
    return x.w < y.w;
  }
};

std::priority_queue<edge, std::vector<edge>, cmp1> wolf;
std::priority_queue<edge, std::vector<edge>, cmp2> human;

const int MAXN = 2e5 + 12;
int dsu1[MAXN], dsu2[MAXN];

int set_of1(int u) {
  if(dsu1[u] == u) return u;
  return dsu1[u] = set_of1(dsu1[u]);
}
int set_of2(int u) {
  if(dsu2[u] == u) return u;
  return dsu2[u] = set_of2(dsu2[u]);
}
void union1(int u, int v) {
  dsu1[set_of1(u)] = set_of1(v);
}
void union2(int u, int v) {
  dsu2[set_of2(u)] = set_of2(v);
}

int rep1[MAXN];
int rep2[MAXN];

std::vector<int> krt_wolf[2 * MAXN];
std::vector<int> krt_human[2 * MAXN];

int wlim_wolf[2 * MAXN];
int wlim_human[2 * MAXN];

int assigned[MAXN];
int stoN;
int q;
int mi[2 * MAXN], ma[2 * MAXN];

int par_wolf[19][2 * MAXN];
int wolfdepth[2 * MAXN];
std::pair<int, int> dfs1(int node, int curdepth) {
  wolfdepth[node] = curdepth;
  if(node < stoN) {
    assigned[node] = q++; 
    mi[node] = ma[node] = assigned[node];
    return {assigned[node], assigned[node]};
  }
  mi[node] = 1e9, ma[node] = -1;
  for(int x: krt_wolf[node]) {
    std::pair<int, int> res = dfs1(x, curdepth + 1);
    mi[node] = std::min(mi[node], res.first);
    ma[node] = std::max(ma[node], res.second);
    par_wolf[0][x] = node;
  }
  return {mi[node], ma[node]};
}

int par_human[19][2 * MAXN];

int A[MAXN];
int humandepth[2 * MAXN];

int rangel[2 * MAXN], ranger[2 * MAXN];

std::pair<int, int> dfs2(int node, int curdepth) {
  humandepth[node] = curdepth;
  if(node < stoN) {
    A[q] = assigned[node]; 
    rangel[node] = ranger[node] = q;
    q++;
    return {rangel[node], ranger[node]};
  }
  rangel[node] = 1e9, ranger[node] = -1;
  for(int x: krt_human[node]) {
    std::pair<int, int> res = dfs2(x, curdepth + 1);
    rangel[node] = std::min(rangel[node], res.first);
    ranger[node] = std::max(ranger[node], res.second);
    par_human[0][x] = node;
  }
  return {rangel[node], ranger[node]};
}


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) {
  stoN = N;
  for(int i=0; i<N; i++) {
    dsu1[i] = dsu2[i] = i;
    rep1[i] = rep2[i] = i;
    wlim_wolf[i] = wlim_human[i] = i; //idk anymore
  }
  int Q = S.size();
  std::vector<int> Answer(Q);
  int M = X.size();
  for(int i=0; i<M; i++) {
    wolf.push({X[i], Y[i], std::max(X[i], Y[i])});
    human.push({X[i], Y[i], std::min(X[i], Y[i])});
  }
  int newnode = N;
  while(wolf.size()) {
    if(set_of1(wolf.top().f) != set_of1(wolf.top().t)) {
      int ff = rep1[set_of1(wolf.top().f)];
      int tt = rep1[set_of1(wolf.top().t)];
      union1(wolf.top().f, wolf.top().t);
      krt_wolf[newnode].push_back(ff);
      krt_wolf[newnode].push_back(tt);
      wlim_wolf[newnode] = wolf.top().w;
      rep1[set_of1(wolf.top().f)] = newnode;
      newnode++;
    }
    wolf.pop();
  }
  int wolfrt = newnode - 1;
  newnode = N;
  while(human.size()) {
    if(set_of2(human.top().f) != set_of2(human.top().t)) {
      int ff = rep2[set_of2(human.top().f)];
      int tt = rep2[set_of2(human.top().t)];
      union2(human.top().f, human.top().t);
      krt_human[newnode].push_back(ff);
      krt_human[newnode].push_back(tt);
      wlim_human[newnode] = human.top().w;
      rep2[set_of2(human.top().f)] = newnode;
      newnode++;
    }
    human.pop();
  }
  int humanrt = newnode - 1;
  
  
  dfs1(wolfrt, 0);
  par_wolf[0][wolfrt] = wolfrt;
  for(int i=1; i<19; i++) {
    for(int j=0; j<=wolfrt; j++) {
      par_wolf[i][j] = par_wolf[i-1][par_wolf[i-1][j]];
    }
  }
  q = 0;
  dfs2(humanrt, 0);
  par_human[0][humanrt] = humanrt;
  for(int i=1; i<19; i++) {
    for(int j=0; j<=humanrt; j++) {
      par_human[i][j] = par_human[i-1][par_human[i-1][j]];
    }
  }

  /*
  std::cout << "wolf\n";
  for(int i=wolfrt; i >= 0; i--) {
    std::cout << "node "<<i<<". weight limit = "<<wlim_wolf[i]<<", node new ids range = [" << mi[i] << ", " << ma[i] << "]\n";
    for(int x: krt_wolf[i]) std::cout << i << ' ' << x << '\n';
  }
  std::cout << "human\n";
  for(int i=humanrt; i >= 0; i--) {
    std::cout << "node " <<i<<". weight limit = "<<wlim_human[i]<<"\n";
    for(int x: krt_human[i]) std::cout << i << ' ' << x << '\n';
  }

  
  for(int i=0; i<N; i++) {
    for(int j=0; j<N; j++) {
      if(assigned[j] == i) {
        std::cout << "order " << i <<": " << j <<"\n";
      }
    }
  }
  */
  /*
  std::cout << "A array:";
  for(int i=0; i<N; i++) std::cout << " " << A[i];
  std::cout << "\n"; 
  */
  for(int i=0; i<Q; i++) {
    for(int j=18; j>=0; j--) {
      if(humandepth[S[i]] >= (1 << j) && wlim_human[par_human[j][S[i]]] >= L[i]) S[i] = par_human[j][S[i]];
      if(wolfdepth[E[i]] >= (1 << j) && wlim_wolf[par_wolf[j][E[i]]] <= R[i]) E[i] = par_wolf[j][E[i]];
    }
    int l = mi[E[i]];
    int r = ma[E[i]];
    int humanl = rangel[S[i]];
    int humanr = ranger[S[i]];
    /*
    std::cout << "query "<<i<<": ";
    std::cout<<S[i]<<" "<<E[i]<<" ";
    std::cout << "human array range [" << humanl << ", " << humanr << "] see see if any element in [" << l << ", " << r << "], ";
    */
    //int res = wlt.upper_bound(humanl, humanr, r + 1);
    int res = -1;
    for(int i = humanl; i <= humanr; i++) {
      if(A[i] <= r) res = std::max(res, A[i]);
    }
    /*
    std::cout << "res=" << res<<"\n";
    */
    if(res != -1 && l <= res && res <= r) {
      Answer[i] = 1;
    }
    else {
      Answer[i] = 0;
    }
    
  }
  return Answer;
}

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 19412 KB Output is correct
2 Correct 11 ms 19412 KB Output is correct
3 Correct 10 ms 19412 KB Output is correct
4 Correct 11 ms 19412 KB Output is correct
5 Correct 11 ms 19428 KB Output is correct
6 Correct 11 ms 19496 KB Output is correct
7 Correct 10 ms 19412 KB Output is correct
8 Correct 10 ms 19492 KB Output is correct
9 Correct 10 ms 19412 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 19412 KB Output is correct
2 Correct 11 ms 19412 KB Output is correct
3 Correct 10 ms 19412 KB Output is correct
4 Correct 11 ms 19412 KB Output is correct
5 Correct 11 ms 19428 KB Output is correct
6 Correct 11 ms 19496 KB Output is correct
7 Correct 10 ms 19412 KB Output is correct
8 Correct 10 ms 19492 KB Output is correct
9 Correct 10 ms 19412 KB Output is correct
10 Correct 23 ms 21204 KB Output is correct
11 Correct 19 ms 21204 KB Output is correct
12 Correct 14 ms 21040 KB Output is correct
13 Correct 19 ms 21292 KB Output is correct
14 Correct 16 ms 21248 KB Output is correct
15 Correct 21 ms 21284 KB Output is correct

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 597 ms 131620 KB Output is correct
2 Execution timed out 4018 ms 139472 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 19412 KB Output is correct
2 Correct 11 ms 19412 KB Output is correct
3 Correct 10 ms 19412 KB Output is correct
4 Correct 11 ms 19412 KB Output is correct
5 Correct 11 ms 19428 KB Output is correct
6 Correct 11 ms 19496 KB Output is correct
7 Correct 10 ms 19412 KB Output is correct
8 Correct 10 ms 19492 KB Output is correct
9 Correct 10 ms 19412 KB Output is correct
10 Correct 23 ms 21204 KB Output is correct
11 Correct 19 ms 21204 KB Output is correct
12 Correct 14 ms 21040 KB Output is correct
13 Correct 19 ms 21292 KB Output is correct
14 Correct 16 ms 21248 KB Output is correct
15 Correct 21 ms 21284 KB Output is correct
16 Correct 597 ms 131620 KB Output is correct
17 Execution timed out 4018 ms 139472 KB Time limit exceeded
18 Halted 0 ms 0 KB -