oj.uz

Submission #85496

# Submission time Handle Problem Language Result Execution time Memory
85496 2018-11-20T14:22:32 Z tmwilliamlin168 Park (JOI17_park) C++14
67 / 100
 407 ms 1024 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))
			continue;
		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 Correct 2 ms 376 KB Output is correct
2 Incorrect 9 ms 500 KB Wrong Answer[3]
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 407 ms 696 KB Output is correct
2 Correct 149 ms 768 KB Output is correct
3 Correct 218 ms 772 KB Output is correct
4 Correct 384 ms 780 KB Output is correct
5 Correct 381 ms 900 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 900 KB Output is correct
2 Correct 210 ms 900 KB Output is correct
3 Correct 219 ms 900 KB Output is correct
4 Correct 186 ms 900 KB Output is correct
5 Correct 248 ms 900 KB Output is correct
6 Correct 218 ms 900 KB Output is correct
7 Correct 215 ms 900 KB Output is correct
8 Correct 236 ms 900 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 900 KB Output is correct
2 Correct 281 ms 900 KB Output is correct
3 Correct 272 ms 900 KB Output is correct
4 Correct 308 ms 900 KB Output is correct
5 Correct 291 ms 900 KB Output is correct
6 Correct 298 ms 900 KB Output is correct
7 Correct 288 ms 900 KB Output is correct
8 Correct 257 ms 900 KB Output is correct
9 Correct 254 ms 900 KB Output is correct
10 Correct 281 ms 972 KB Output is correct
11 Correct 280 ms 972 KB Output is correct
12 Correct 247 ms 972 KB Output is correct
13 Correct 304 ms 972 KB Output is correct
14 Correct 269 ms 972 KB Output is correct
15 Correct 313 ms 972 KB Output is correct
16 Correct 222 ms 972 KB Output is correct
17 Correct 385 ms 972 KB Output is correct
18 Correct 265 ms 972 KB Output is correct
19 Correct 345 ms 972 KB Output is correct
20 Correct 271 ms 972 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 342 ms 972 KB Output is correct
2 Correct 315 ms 972 KB Output is correct
3 Correct 283 ms 972 KB Output is correct
4 Incorrect 249 ms 1024 KB Wrong Answer[3]
5 Halted 0 ms 0 KB -