| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 72805 |
2018-08-27T02:27:02 Z |
Benq |
Park (JOI17_park) |
C++14 |
|
238 ms |
34336 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];
// BEGIN UTILITY
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;
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 answer(int l, int r) {
if (l > r) swap(l,r);
Answer(l,r);
}
// END UTILITY
bool inTree[1400];
vi divi(int l, int r) {
if (checkEdge(l,r)) { answer(l,r); return {r}; }
vi tmp;
F0R(i,n) if (i != l && i != r && !inTree[i]) 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;
}
return merge(divi(l,tmp[lo-1]),divi(tmp[lo-1],r));
}
int getAdj(int x, vi cur) {
vi bad; F0R(i,n) if (!inTree[i] && i != x) bad.pb(i);
int lo = 1, hi = sz(cur);
while (lo < hi) {
int mid = (lo+hi)/2;
if (ok(cur[0],x,vi(cur.begin(),cur.begin()+mid))) hi = mid;
else lo = mid+1;
}
return cur[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);
return;
}
inTree[0] = 1;
vi cur = {0};
int nex = 0;
while (nex < n) {
while (nex < n && inTree[nex]) nex ++;
if (nex == n) return;
int x = getAdj(nex,cur);
vi t = divi(x,nex);
for (int i: t) { cur.pb(i); inTree[i] = 1; }
}
}
#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) {
cout << A << " " << 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 |
2 ms |
248 KB |
Output is correct |
| 2 |
Correct |
13 ms |
484 KB |
Output is correct |
| 3 |
Correct |
13 ms |
536 KB |
Output is correct |
| 4 |
Correct |
13 ms |
536 KB |
Output is correct |
| 5 |
Correct |
15 ms |
592 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
47 ms |
804 KB |
Output is correct |
| 2 |
Correct |
106 ms |
804 KB |
Output is correct |
| 3 |
Correct |
87 ms |
2876 KB |
Output is correct |
| 4 |
Correct |
50 ms |
2876 KB |
Output is correct |
| 5 |
Correct |
43 ms |
2876 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
183 ms |
34336 KB |
Wrong Answer[5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
238 ms |
34336 KB |
Wrong Answer[5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
34336 KB |
Wrong Answer[3] |
| 2 |
Halted |
0 ms |
0 KB |
- |
