oj.uz

Submission #85494

# Submission time Handle Problem Language Result Execution time Memory
85494 2018-11-20T14:13:32 Z tmwilliamlin168 Park (JOI17_park) C++14
67 / 100
 416 ms 976 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)
			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 415 ms 640 KB Output is correct
2 Correct 151 ms 684 KB Output is correct
3 Correct 222 ms 840 KB Output is correct
4 Correct 407 ms 840 KB Output is correct
5 Correct 410 ms 840 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 840 KB Output is correct
2 Correct 219 ms 840 KB Output is correct
3 Correct 232 ms 936 KB Output is correct
4 Correct 193 ms 936 KB Output is correct
5 Correct 249 ms 936 KB Output is correct
6 Correct 231 ms 936 KB Output is correct
7 Correct 202 ms 936 KB Output is correct
8 Correct 224 ms 936 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 936 KB Output is correct
2 Correct 292 ms 936 KB Output is correct
3 Correct 289 ms 936 KB Output is correct
4 Correct 280 ms 936 KB Output is correct
5 Correct 317 ms 948 KB Output is correct
6 Correct 304 ms 948 KB Output is correct
7 Correct 309 ms 964 KB Output is correct
8 Correct 279 ms 964 KB Output is correct
9 Correct 280 ms 964 KB Output is correct
10 Correct 304 ms 976 KB Output is correct
11 Correct 301 ms 976 KB Output is correct
12 Correct 279 ms 976 KB Output is correct
13 Correct 342 ms 976 KB Output is correct
14 Correct 274 ms 976 KB Output is correct
15 Correct 416 ms 976 KB Output is correct
16 Correct 228 ms 976 KB Output is correct
17 Correct 412 ms 976 KB Output is correct
18 Correct 282 ms 976 KB Output is correct
19 Correct 361 ms 976 KB Output is correct
20 Correct 293 ms 976 KB Output is correct

Subtask #5
0 / 23.0

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