oj.uz

Submission #995924

# Submission time Handle Problem Language Result Execution time Memory
995924 2024-06-10T04:14:02 Z 12345678 Park (JOI17_park) C++17
67 / 100
 106 ms 852 KB 
#include "park.h"
#include <bits/stdc++.h>

using namespace std;

const int nx=1500;

static int Place[1400];

int n, pa[nx], used[nx], add[nx], l, r;
vector<int> d[nx], x;

void dfs(int u)
{
	x.push_back(u);
	for (auto v:d[u]) dfs(v);
}

void solve(int u)
{
	used[u]=1;
	for (int i=0; i<n; i++) Place[i]=used[i];
	if (Ask(0, u, Place)) return;
	int l=0, r=n-1;
	while (l<r)
	{
		int md=(l+r)/2;
		for (int i=0; i<n; i++) Place[i]=used[i];
		for (int i=0; i<=md; i++) Place[i]=1;
		if (Ask(0, u, Place)) r=md;
		else l=md+1;
	}
	pa[l]=pa[u];
	pa[u]=l;
	solve(l);
	solve(u);
}

void Detect(int T, int N) {
	n=N;
	used[0]=add[0]=1;
	for (int i=1; i<N; i++) 
	{
		if (used[i]) continue;
		x.clear();
		dfs(0);
		l=0, r=x.size()-1;
		while (l<r)
		{
			int md=(l+r)/2;
			for (int j=0; j<N; j++) Place[j]=1;
			for (int j=md+1; j<x.size(); j++) Place[x[j]]=0;
			if (Ask(0, i, Place)) r=md;
			else l=md+1;
		}
		pa[i]=x[l];
		solve(i);
		int u=i;
		while (!add[u]) add[u]=1, d[pa[u]].push_back(u), u=pa[u];
	}
	//for (int i=1; i<N; i++) cout<<"pa "<<i<<' '<<pa[i]<<'\n';
	for (int i=1; i<N; i++) Answer(min(i, pa[i]), max(i, pa[i]));
}

Compilation message

park.cpp: In function 'void Detect(int, int)':
park.cpp:52:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |    for (int j=md+1; j<x.size(); j++) Place[x[j]]=0;
      |                     ~^~~~~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 676 KB Output is correct
2 Correct 68 ms 604 KB Output is correct
3 Correct 70 ms 664 KB Output is correct
4 Correct 100 ms 604 KB Output is correct
5 Correct 101 ms 604 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 604 KB Output is correct
2 Correct 79 ms 604 KB Output is correct
3 Correct 76 ms 604 KB Output is correct
4 Correct 71 ms 604 KB Output is correct
5 Correct 79 ms 604 KB Output is correct
6 Correct 77 ms 604 KB Output is correct
7 Correct 74 ms 608 KB Output is correct
8 Correct 75 ms 604 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 580 KB Output is correct
2 Correct 97 ms 604 KB Output is correct
3 Correct 83 ms 604 KB Output is correct
4 Correct 94 ms 604 KB Output is correct
5 Correct 95 ms 644 KB Output is correct
6 Correct 94 ms 604 KB Output is correct
7 Correct 89 ms 604 KB Output is correct
8 Correct 93 ms 604 KB Output is correct
9 Correct 88 ms 624 KB Output is correct
10 Correct 99 ms 852 KB Output is correct
11 Correct 96 ms 632 KB Output is correct
12 Correct 85 ms 604 KB Output is correct
13 Correct 105 ms 632 KB Output is correct
14 Correct 89 ms 624 KB Output is correct
15 Correct 106 ms 624 KB Output is correct
16 Correct 76 ms 604 KB Output is correct
17 Correct 101 ms 652 KB Output is correct
18 Correct 105 ms 604 KB Output is correct
19 Correct 102 ms 612 KB Output is correct
20 Correct 93 ms 604 KB Output is correct

Subtask #5
0 / 23.0

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