oj.uz

Submission #61208

# Submission time Handle Problem Language Result Execution time Memory
61208 2018-07-25T11:21:52 Z upsolving(#1740) Park (JOI17_park) C++11
67 / 100
 187 ms 1604 KB 
#include "park.h"
#include<cstdio>
#include<algorithm>
#include<vector>
#define N_ 1400
using namespace std;

vector<int>E[N_];

static int Place[N_];
int chk[N_], L[N_], cnt, n;
void DFS(int a) {
	L[++cnt] = a;
	for (auto &x : E[a]) {
		DFS(x);
	}
}

int Ask2(int a, int b) {
	Place[a] = Place[b] = 1;
	return Ask(min(a, b), max(a, b), Place);
}

void Make(int p, int a) {
	int b = 0, e = n, mid, r = 0, i;
	while (b <= e) {
		mid = (b + e) >> 1;
		for (i = 0; i < mid; i++) Place[i] = 1;
		for (i = i; i < n; i++) Place[i] = 0;
		if (Ask2(p, a)) {
			r = mid;
			e = mid - 1;
		}
		else b = mid + 1;
	}
	if (!r) {
		E[p].push_back(a);
	}
	else {
		Make(p, r - 1);
		Make(r - 1, a);
	}
	chk[a] = 1;
}

void Add(int a) {
	int i, j;
	cnt = 0;
	DFS(0);
	int b = 1, e = cnt, mid, r = 0;
	while (b <= e) {
		mid = (b + e) >> 1;
		for (i = 0; i < n; i++)Place[i] = 1;
		for (i = mid + 1; i <= cnt; i++)Place[L[i]] = 0;
		if (Ask2(0, a)) {
			r = mid;
			e = mid - 1;
		}
		else b = mid + 1;
	}
	
	Make(L[r], a);

}
void Detect(int T, int N) {
	int i;
	chk[0] = 1;
	n = N;
	for (i = 1; i < N; i++) {
		if (!chk[i]) {
			Add(i);
		}
	}
	for (i = 0; i < N; i++) {
		for (auto &x : E[i]) {
			Answer(min(x, i), max(x, i));
		}
	}
}

Compilation message

park.cpp: In function 'void Add(int)':
park.cpp:47:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Wrong Answer[3]
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 616 KB Output is correct
2 Correct 168 ms 748 KB Output is correct
3 Correct 139 ms 964 KB Output is correct
4 Correct 71 ms 964 KB Output is correct
5 Correct 78 ms 1064 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 1064 KB Output is correct
2 Correct 187 ms 1064 KB Output is correct
3 Correct 132 ms 1064 KB Output is correct
4 Correct 183 ms 1100 KB Output is correct
5 Correct 139 ms 1144 KB Output is correct
6 Correct 118 ms 1144 KB Output is correct
7 Correct 144 ms 1192 KB Output is correct
8 Correct 165 ms 1192 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 1216 KB Output is correct
2 Correct 141 ms 1216 KB Output is correct
3 Correct 131 ms 1256 KB Output is correct
4 Correct 109 ms 1276 KB Output is correct
5 Correct 124 ms 1296 KB Output is correct
6 Correct 113 ms 1296 KB Output is correct
7 Correct 77 ms 1296 KB Output is correct
8 Correct 110 ms 1296 KB Output is correct
9 Correct 111 ms 1296 KB Output is correct
10 Correct 135 ms 1380 KB Output is correct
11 Correct 141 ms 1460 KB Output is correct
12 Correct 137 ms 1460 KB Output is correct
13 Correct 90 ms 1460 KB Output is correct
14 Correct 115 ms 1460 KB Output is correct
15 Correct 121 ms 1504 KB Output is correct
16 Correct 130 ms 1504 KB Output is correct
17 Correct 56 ms 1504 KB Output is correct
18 Correct 176 ms 1504 KB Output is correct
19 Correct 94 ms 1504 KB Output is correct
20 Correct 140 ms 1504 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 1604 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -