oj.uz

Submission #85495

# Submission time Handle Problem Language Result Execution time Memory
85495 2018-11-20T14:16:54 Z tmwilliamlin168 Park (JOI17_park) C++14
67 / 100
 437 ms 952 KB 
#include "park.h"
#include <bits/stdc++.h>
using namespace std;

const int mxN=1400;
int n, p[mxN], a[mxN], d[mxN], e[mxN][7];
vector<int> dl;
bool vis[mxN];

void ae(int u, int v) {
	e[u][d[u]++]=v;
	e[v][d[v]++]=u;
	Answer(min(u, v), max(u, v));
}

void dfs(int u) {
	vis[u]=1;
	dl.push_back(u);
	for(int i=0; i<d[u]; ++i)
		if(!vis[e[u][i]]&&a[e[u][i]]!=3)
			dfs(e[u][i]);
}

void b(int u) {
	a[u]=2;
	while(1) {
		for(int i=0; i<n; ++i)
			p[i]=a[i]==1;
		p[u]=1;
		if(Ask(0, u, p))
			break;
		int lb=0, rb=n-1;
		while(lb<rb) {
			int mb=(lb+rb)/2;
			for(int i=0; i<n; ++i)
				p[i]=a[i]==1||!a[i]&&i<=mb;
			p[u]=1;
			if(Ask(0, u, p))
				rb=mb;
			else
				lb=mb+1;
		}
		b(lb);
	}
	vector<int> f{0};
	for(int i=0; i<f.size(); ++i) {
		memset(vis, 0, n);
		dl.clear();
		dfs(f[i]);
		memset(p, 0, 4*n);
		for(int di : dl)
			p[di]=1;
		p[u]=1;
		if(!Ask(min(f[i], u), max(f[i], u), p))
			break;
		int lb=0, rb=dl.size()-1;
		while(lb<rb) {
			int mb=(lb+rb)/2;
			memset(p, 0, 4*n);
			for(int j=0; j<=mb; ++j)
				p[dl[j]]=1;
			p[u]=1;
			if(Ask(min(f[i], u), max(f[i], u), p))
				rb=mb;
			else
				lb=mb+1;
		}
		for(int j=0; j<d[dl[lb]]; ++j)
			if(a[e[dl[lb]][j]]!=3)
				f.push_back(e[dl[lb]][j]);
		ae(u, dl[lb]);
		a[dl[lb]]=3;
	}
	for(int i=0; i<n; ++i)
		if(a[i]==3||i==u)
			a[i]=1;
}

void Detect(int T, int N) {
	n=N;
	a[0]=1;
	for(int i=1; i<n; ++i)
		if(!a[i])
			b(i);
}

Compilation message

park.cpp: In function 'void b(int)':
park.cpp:36:24: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
     p[i]=a[i]==1||!a[i]&&i<=mb;
                   ~~~~~^~~~~~~
park.cpp:46:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<f.size(); ++i) {
               ~^~~~~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 437 ms 764 KB Output is correct
2 Correct 165 ms 768 KB Output is correct
3 Correct 200 ms 768 KB Output is correct
4 Correct 436 ms 836 KB Output is correct
5 Correct 414 ms 836 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 836 KB Output is correct
2 Correct 235 ms 836 KB Output is correct
3 Correct 259 ms 836 KB Output is correct
4 Correct 193 ms 836 KB Output is correct
5 Correct 263 ms 836 KB Output is correct
6 Correct 216 ms 836 KB Output is correct
7 Correct 211 ms 836 KB Output is correct
8 Correct 226 ms 836 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 836 KB Output is correct
2 Correct 306 ms 836 KB Output is correct
3 Correct 285 ms 836 KB Output is correct
4 Correct 287 ms 836 KB Output is correct
5 Correct 313 ms 848 KB Output is correct
6 Correct 309 ms 848 KB Output is correct
7 Correct 356 ms 848 KB Output is correct
8 Correct 350 ms 848 KB Output is correct
9 Correct 279 ms 856 KB Output is correct
10 Correct 310 ms 856 KB Output is correct
11 Correct 337 ms 856 KB Output is correct
12 Correct 278 ms 856 KB Output is correct
13 Correct 334 ms 856 KB Output is correct
14 Correct 289 ms 856 KB Output is correct
15 Correct 349 ms 856 KB Output is correct
16 Correct 253 ms 952 KB Output is correct
17 Correct 415 ms 952 KB Output is correct
18 Correct 285 ms 952 KB Output is correct
19 Correct 360 ms 952 KB Output is correct
20 Correct 293 ms 952 KB Output is correct

Subtask #5
0 / 23.0

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