oj.uz

Submission #64095

# Submission time Handle Problem Language Result Execution time Memory
64095 2018-08-03T10:57:21 Z Just_Solve_The_Problem popa (BOI18_popa) C++11
0 / 100
 1000 ms 376 KB 
#include "popa.h"
#include <bits/stdc++.h>

#define pb push_back
#define pii pair < int, int >
#define fr first
#define sc second
#define mk make_pair

using namespace std;

int tab[123][123];
pii ar[123];
int used[123];

//int query(int a, int b, int c, int d);

int solve(int n, int left[], int right[]) {
  if (n != 100) return 0;
  for (int i = 0; i < n; i++)
    left[i] = right[i] = -1;
  int root = 0;
  int mx = 0;
  for (int i = 0; i < n; i++) {
    int len = 0;
    for (int j = 0; j < n; j++) {
      if (j == i) continue;
      tab[i][j] = query(i, i, j, j);
      if (tab[i][j]) {
        len++;
      }
    }
    ar[i] = mk(len, i);
  }
  sort(ar, ar + n);
  reverse(ar, ar + n);
  root = ar[0].sc;
  queue < int > q;
  q.push(root);
  int cur = 1;
  used[0] = 1;
  while (!q.empty()) {
    int v = q.front();
    q.pop();
    int mx = -1;
    for (int i = 0; i < n; i++) {
      if (used[ar[i].sc]) continue;
      if (tab[v][ar[i].sc]) {
        mx = ar[i].sc;
        break;
      }
    }
    if (mx != -1) {
      used[mx] = 1;
      left[v] = mx;
      q.push(mx);
    }
    mx = -1;
    for (int i = 0; i < n; i++) {
      if (used[ar[i].sc]) continue;
      if (tab[v][ar[i].sc]) {
        mx = ar[i].sc;
        break;
      }
    }
    if (mx != -1) {
      used[mx] = 1;
      right[mx] = mx;
      q.push(mx);
    }
  }
  return root;
}

Compilation message

popa.cpp: In function 'int solve(int, int*, int*)':
popa.cpp:23:7: warning: unused variable 'mx' [-Wunused-variable]
   int mx = 0;
       ^~
popa.cpp:40:7: warning: unused variable 'cur' [-Wunused-variable]
   int cur = 1;
       ^~~

Subtask #1
0 / 37.0

# Verdict Execution time Memory Grader output
1 Incorrect 94 ms 376 KB not a valid binary tree
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1076 ms 376 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 39.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1070 ms 376 KB Time limit exceeded
2 Halted 0 ms 0 KB -