| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 72794 |
2018-08-27T00:53:24 Z |
Benq |
Park (JOI17_park) |
C++14 |
|
148 ms |
12092 KB |
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;
#define NMAX 1400
#define DMAX 1400
#define QMAX 45000
// #define LOCAL
#ifndef LOCAL
#include "park.h"
#else
void Answer(int A, int B);
int Ask(int A, int B, int Place[]);
#endif
int n;
static int Place[1400];
bool ok(int a, int b, vi x) {
if (a > b) swap(a,b);
F0R(i,1400) Place[i] = 0;
Place[a] = Place[b] = 1;
for (int i: x) Place[i] = 1;
/*if (a == 51 || b == 51) {
F0R(i,1400) if (Place[i]) cout << i << "\n";
}*/
return Ask(a,b,Place);
}
bool checkEdge(int a, int b) { return ok(a,b,{}); }
vi merge(vi a, vi b) {
a.insert(a.end(),all(b));
return a;
}
void divi(int l, int r) {
if (checkEdge(l,r)) { Answer(min(l,r),max(l,r)); return; }
vi tmp;
F0R(i,n) if (i != l && i != r) tmp.pb(i);
int lo = 1, hi = sz(tmp);
while (lo < hi) {
int mid = (lo+hi)/2;
if (ok(l,r,vi(tmp.begin(),tmp.begin()+mid))) hi = mid;
else lo = mid+1;
}
divi(l,tmp[lo-1]); divi(tmp[lo-1],r);
}
void test(int i, vi tre, vi lst) {
int lo = 1, hi = sz(lst);
while (lo < hi) {
int mid = (lo+hi)/2;
if (ok(i,0,merge(tre,vi(lst.begin(),lst.begin()+mid)))) hi = mid;
else lo = mid+1;
}
Answer(min(i,lst[lo-1]),max(i,lst[lo-1]));
}
void Detect(int T, int _n) {
n = _n;
if (T == 1) {
F0R(i,n) FOR(j,i+1,n) if (checkEdge(i,j)) Answer(i,j);
}
if (T == 2) {
divi(0,n-1);
}
if (T == 3) {
bool inTree[1400]; F0R(i,1400) inTree[i] = 0;
inTree[0] = 1;
vi tre, lst = {0};
int co = 0;
while (sz(tre)+sz(lst) < n) {
co ++;
vi TRE = merge(tre,lst);
vi tmp;
F0R(i,n) if (!inTree[i]) {
if (ok(lst[0],i,TRE)) {
tmp.pb(i);
inTree[i] = 1;
}
}
for (int i: tmp) test(i,tre,lst);
tre = TRE; lst = tmp;
}
}
}
#ifdef LOCAL
static int T,N,M,Asktotal,Answertotal;
static int edge_list[NMAX][DMAX];
static int checked[NMAX][DMAX];
static int degree[NMAX];
static int visited[NMAX];
static void WA(int wa_num) {
printf("Wrong Answer[%d]\n",wa_num);
exit(0);
}
void Answer(int A, int B) {
int i;
if(A < 0||A >= B||B >= N) WA(1);
for(i = 0 ; i < degree[A] ; i++) {
if(edge_list[A][i] == B) {
if(checked[A][i] == 1) {
cout << "BAD " << A << " " << B << "\n";
WA(3);
}
Answertotal++;
checked[A][i] = 1;
return;
}
}
WA(2);
}
static void dfs(int now, int Place[], bool z = 0) {
visited[now] = 1;
// if (z) cout << "AAA " << now << "\n";
int i;
for(i = 0 ; i < degree[now] ; i++) {
if(visited[edge_list[now][i]] == 0 && Place[edge_list[now][i]] == 1) {
// if (edge_list[now][i] == 51) cout << "BBB " << now << " " << i << " " << edge_list[now][i] << "\n";
dfs(edge_list[now][i], Place,z);
}
}
}
int Ask(int A, int B, int Place[]) {
/*if (A == 1 && B == 51) {
cout << "AA " << A << " " << B << "\n";
F0R(i,1400) if (Place[i]) cout << "RES " << i << "\n";
}*/
int i;
Asktotal++;
if(Asktotal>QMAX) WA(5);
if(A < 0||A >= B||B >= N) WA(4);
if(Place[A] != 1) WA(4);
if(Place[B] != 1) WA(4);
for(i = 0 ; i < N ; i++) {
if(Place[i]<0||Place[i]>1) WA(4);
visited[i] = 0;
}
dfs(A, Place);
/*if (A == 1 && B == 51) {
cout << "BB " << B << " " << visited[B];
exit(0);
}*/
return visited[B];
}
int main(int argc, char **argv) {
int i;
scanf("%d%d%d",&T,&N,&M);
Answertotal = 0;
for(i = 0 ; i < N ; i++) degree[i] = 0;
for(i = 0 ; i < M ; i++) {
int ea,eb;
scanf("%d%d",&ea,&eb);
checked[ea][degree[ea]] = 0;
checked[eb][degree[eb]] = 0;
edge_list[ea][degree[ea]++] = eb;
edge_list[eb][degree[eb]++] = ea;
/*if (eb == 10) {
cout << "RU " << edge_list[10][0] << "\n";
}
if (ea == 10 || eb == 10) cout << "ZZZZZ " << ea << " " << eb << "\n";*/
}
Detect(T, N);
if(Answertotal<M) WA(6);
printf("Accepted\n");
return 0;
}
#endif
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
248 KB |
Output is correct |
| 2 |
Correct |
17 ms |
356 KB |
Output is correct |
| 3 |
Correct |
12 ms |
432 KB |
Output is correct |
| 4 |
Correct |
11 ms |
448 KB |
Output is correct |
| 5 |
Correct |
11 ms |
448 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
43 ms |
764 KB |
Output is correct |
| 2 |
Correct |
148 ms |
12092 KB |
Output is correct |
| 3 |
Correct |
115 ms |
12092 KB |
Output is correct |
| 4 |
Correct |
46 ms |
12092 KB |
Output is correct |
| 5 |
Correct |
47 ms |
12092 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
110 ms |
12092 KB |
Output is correct |
| 2 |
Correct |
143 ms |
12092 KB |
Output is correct |
| 3 |
Correct |
133 ms |
12092 KB |
Output is correct |
| 4 |
Correct |
113 ms |
12092 KB |
Output is correct |
| 5 |
Correct |
130 ms |
12092 KB |
Output is correct |
| 6 |
Correct |
127 ms |
12092 KB |
Output is correct |
| 7 |
Correct |
119 ms |
12092 KB |
Output is correct |
| 8 |
Correct |
138 ms |
12092 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
12092 KB |
Wrong Answer[6] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
12092 KB |
Wrong Answer[6] |
| 2 |
Halted |
0 ms |
0 KB |
- |
