oj.uz

Submission #85497

# Submission time Handle Problem Language Result Execution time Memory
85497 2018-11-20T14:29:45 Z tmwilliamlin168 Park (JOI17_park) C++14
100 / 100
 424 ms 1272 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) {
		if(a[f[i]]==3)
			continue;
		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)
			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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 11 ms 444 KB Output is correct
3 Correct 9 ms 560 KB Output is correct
4 Correct 28 ms 560 KB Output is correct
5 Correct 76 ms 580 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 396 ms 740 KB Output is correct
2 Correct 138 ms 740 KB Output is correct
3 Correct 210 ms 860 KB Output is correct
4 Correct 424 ms 912 KB Output is correct
5 Correct 412 ms 912 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 912 KB Output is correct
2 Correct 240 ms 912 KB Output is correct
3 Correct 235 ms 912 KB Output is correct
4 Correct 186 ms 912 KB Output is correct
5 Correct 283 ms 912 KB Output is correct
6 Correct 217 ms 912 KB Output is correct
7 Correct 238 ms 912 KB Output is correct
8 Correct 233 ms 912 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 912 KB Output is correct
2 Correct 322 ms 912 KB Output is correct
3 Correct 289 ms 920 KB Output is correct
4 Correct 275 ms 920 KB Output is correct
5 Correct 300 ms 920 KB Output is correct
6 Correct 318 ms 944 KB Output is correct
7 Correct 354 ms 944 KB Output is correct
8 Correct 269 ms 944 KB Output is correct
9 Correct 268 ms 944 KB Output is correct
10 Correct 292 ms 944 KB Output is correct
11 Correct 291 ms 944 KB Output is correct
12 Correct 255 ms 1076 KB Output is correct
13 Correct 311 ms 1076 KB Output is correct
14 Correct 269 ms 1076 KB Output is correct
15 Correct 319 ms 1076 KB Output is correct
16 Correct 233 ms 1076 KB Output is correct
17 Correct 392 ms 1076 KB Output is correct
18 Correct 264 ms 1076 KB Output is correct
19 Correct 365 ms 1076 KB Output is correct
20 Correct 298 ms 1076 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 357 ms 1076 KB Output is correct
2 Correct 335 ms 1076 KB Output is correct
3 Correct 297 ms 1076 KB Output is correct
4 Correct 290 ms 1076 KB Output is correct
5 Correct 378 ms 1076 KB Output is correct
6 Correct 400 ms 1076 KB Output is correct
7 Correct 353 ms 1076 KB Output is correct
8 Correct 321 ms 1116 KB Output is correct
9 Correct 311 ms 1144 KB Output is correct
10 Correct 268 ms 1144 KB Output is correct
11 Correct 297 ms 1144 KB Output is correct
12 Correct 308 ms 1236 KB Output is correct
13 Correct 261 ms 1236 KB Output is correct
14 Correct 344 ms 1272 KB Output is correct
15 Correct 310 ms 1272 KB Output is correct
16 Correct 226 ms 1272 KB Output is correct
17 Correct 383 ms 1272 KB Output is correct
18 Correct 285 ms 1272 KB Output is correct