oj.uz

Submission #85493

# Submission time Handle Problem Language Result Execution time Memory
85493 2018-11-20T13:52:15 Z tmwilliamlin168 Park (JOI17_park) C++14
67 / 100
 428 ms 1680 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) {
		while(a[f[i]]!=3) {
			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(e[dl[lb]][j]>dl[lb])
					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 10 ms 376 KB Wrong Answer[6]
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 428 ms 544 KB Output is correct
2 Correct 143 ms 652 KB Output is correct
3 Correct 222 ms 688 KB Output is correct
4 Correct 417 ms 852 KB Output is correct
5 Correct 425 ms 932 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 932 KB Output is correct
2 Correct 239 ms 932 KB Output is correct
3 Correct 274 ms 932 KB Output is correct
4 Correct 203 ms 932 KB Output is correct
5 Correct 304 ms 1084 KB Output is correct
6 Correct 264 ms 1084 KB Output is correct
7 Correct 216 ms 1084 KB Output is correct
8 Correct 242 ms 1208 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 1208 KB Output is correct
2 Correct 298 ms 1208 KB Output is correct
3 Correct 294 ms 1208 KB Output is correct
4 Correct 296 ms 1240 KB Output is correct
5 Correct 333 ms 1364 KB Output is correct
6 Correct 316 ms 1364 KB Output is correct
7 Correct 313 ms 1364 KB Output is correct
8 Correct 275 ms 1368 KB Output is correct
9 Correct 288 ms 1368 KB Output is correct
10 Correct 305 ms 1368 KB Output is correct
11 Correct 299 ms 1400 KB Output is correct
12 Correct 272 ms 1420 KB Output is correct
13 Correct 325 ms 1440 KB Output is correct
14 Correct 285 ms 1496 KB Output is correct
15 Correct 338 ms 1496 KB Output is correct
16 Correct 240 ms 1496 KB Output is correct
17 Correct 415 ms 1548 KB Output is correct
18 Correct 278 ms 1632 KB Output is correct
19 Correct 368 ms 1632 KB Output is correct
20 Correct 297 ms 1632 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 404 ms 1632 KB Output is correct
2 Correct 324 ms 1632 KB Output is correct
3 Incorrect 294 ms 1680 KB Wrong Answer[6]
4 Halted 0 ms 0 KB -