oj.uz

답안 #150545

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
150545 2019-09-01T08:36:59 Z 1 WA = 5 Push Up(#3624, BaaaaaaaaaaaaaaaarkingDog, IohcEjnim, 0xrgb) 로카히아 유적 (FXCUP4_lokahia) C++17
0 / 100
 7 ms 688 KB 
#include "lokahia.h"
#include <stdlib.h>
#include <algorithm>
#include <stdio.h>
using namespace std;
int p[706];
int query[706][3];

int find(int a){
  if(p[a] < 0) return a;
  return p[a] = find(p[a]);
}
int uni(int a, int b){
  a = find(a);
  b = find(b);
  if(a==b) return 0;
  p[a] += p[b];
  p[b] = a;
  return -p[a];
}

int mysize(int a){
  if(p[a] < 0) return -p[a];
  return mysize(p[a]);
}

int shu[206];
int FindBase(int N){
  srand(234316);
  int GROUP_IDX = N+1;
  if(N==1) return 0;
  for(int i = 0; i < 700; i++){
    p[i] = -1;
  }
  for(int i = 0; i < N; i++) shu[i] = i;
  for(int i = N-1; i >= 1; i--){
    int j = rand()%i;
    swap(shu[i], shu[j]);
  }
  int GUESS_IDX = 0;
  while(GUESS_IDX < 400){
    int a = 0, b = 0;
    while(find(a) == find(b)){      
      if(GUESS_IDX < N-1){
        a = shu[GUESS_IDX];
        b = shu[GUESS_IDX+1];
      }
      if(find(a)==find(b)){
        a = rand()%N;
        b = rand()%N;
      }
      //printf("%d %d %d %d\n",a,b,find(a),find(b));
    }
    int ret = CollectRelics(a,b);
    //printf("%d %d %d\n",a,b,ret);
    query[GUESS_IDX][0]=a;
    query[GUESS_IDX][1]=b;
    query[GUESS_IDX][2]=ret;
    if(ret != -1){
      uni(a, b);
      uni(a,ret);
      int sz = mysize(a);
      if(sz > N/2){
        int ret = -1;
        for(int i = 0; i < GUESS_IDX; i++){
          if(find(query[GUESS_IDX][0]) != find(a) or find(query[GUESS_IDX][1]) != find(a)) continue;
          ret = max(ret, query[GUESS_IDX][2]);         
        }
        return ret;
      }
    }
    GUESS_IDX++;
  }
  int mxidx = 0;
  for(int i = 0; i < N; i++){
    if(mysize(i) > mysize(mxidx)) mxidx = i;
  }
	int ret = -1;
  for(int i = 0; i < GUESS_IDX; i++){
    if(find(query[GUESS_IDX][0]) != find(mxidx) or find(query[GUESS_IDX][1]) != find(mxidx)) continue;
    ret = max(ret, query[GUESS_IDX][2]);
  }
  int cnt = 1;
  for(int i = 0; i < N; i++){
    if(i==ret) continue;
    if(CollectRelics(i,ret) != -1) cnt++;
  }
  if(cnt > N/2) return ret;
  else return -1;
}

Compilation message

lokahia.cpp: In function 'int FindBase(int)':
lokahia.cpp:30:7: warning: unused variable 'GROUP_IDX' [-Wunused-variable]
   int GROUP_IDX = N+1;
       ^~~~~~~~~

Subtask #1
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 512 KB Correct : C = 176
2 Incorrect 6 ms 640 KB Wrong
3 Correct 6 ms 640 KB Correct : C = 213
4 Partially correct 5 ms 512 KB Partially correct : C = 383
5 Correct 6 ms 512 KB Correct : C = 59
6 Incorrect 5 ms 512 KB Wrong
7 Incorrect 6 ms 640 KB Wrong
8 Correct 6 ms 512 KB Correct : C = 284
9 Incorrect 6 ms 640 KB Wrong
10 Correct 6 ms 640 KB Correct : C = 253
11 Incorrect 6 ms 640 KB Wrong
12 Incorrect 6 ms 640 KB Wrong
13 Partially correct 6 ms 640 KB Partially correct : C = 599
14 Partially correct 7 ms 512 KB Partially correct : C = 519
15 Correct 5 ms 512 KB Correct : C = 0
16 Incorrect 6 ms 512 KB Wrong
17 Partially correct 5 ms 512 KB Partially correct : C = 518
18 Incorrect 6 ms 640 KB Wrong
19 Correct 6 ms 512 KB Correct : C = 295
20 Incorrect 6 ms 640 KB Wrong
21 Incorrect 5 ms 512 KB Wrong
22 Correct 6 ms 640 KB Correct : C = 99
23 Incorrect 6 ms 640 KB Wrong
24 Partially correct 5 ms 640 KB Partially correct : C = 598
25 Correct 6 ms 512 KB Correct : C = 59
26 Partially correct 7 ms 688 KB Partially correct : C = 599
27 Correct 6 ms 640 KB Correct : C = 98