| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 72987 |
2018-08-27T12:11:04 Z |
Benq |
Park (JOI17_park) |
C++14 |
|
227 ms |
2904 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;
}
bool inTree[1400];
vi adj[1400], tmp;
void answer(int l, int r) {
if (l > r) swap(l,r);
adj[l].pb(r), adj[r].pb(l);
Answer(l,r);
}
// END UTILITY
vi divi(int l, int r) {
// cout << "BLAH " << l << " " << r << "\n";
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,merge(bad,vi(cur.begin(),cur.begin()+mid)))) hi = mid;
else lo = mid+1;
}
return cur[lo-1];
}
bool OK[1400];
void dfs(int i) {
tmp.pb(i); OK[i] = 0;
for (int j: adj[i]) if (OK[j]) dfs(j);
}
vector<vi> rem(vi cur, int ol) {
F0R(i,1400) OK[i] = 0;
for (int i: cur) if (i != ol) OK[i] = 1;
vector<vi> res;
for (int i: cur) if (OK[i]) {
dfs(i);
res.pb(tmp); tmp = {};
}
return res;
}
void tri(vi x, int ne) {
if (!sz(x)) return;
if (!ok(x[0],ne,x)) return;
int y = getAdj(ne,x);
answer(ne,y);
for (auto z: rem(x,y)) tri(z,ne);
}
void ad(vi cur, int ne, int ol) {
auto a = rem(cur,ol);
for (auto x: a) tri(x,ne);
}
void Detect(int T, int _n) {
n = _n;
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) { inTree[i] = 1; ad(cur,i,x); cur.pb(i); x = i; }
}
}
#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;
cout << A << " " << B << "\n";
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) {
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 |
Incorrect |
3 ms |
376 KB |
Wrong Answer[2] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
87 ms |
744 KB |
Output is correct |
| 2 |
Correct |
148 ms |
748 KB |
Output is correct |
| 3 |
Correct |
136 ms |
2904 KB |
Output is correct |
| 4 |
Correct |
90 ms |
2904 KB |
Output is correct |
| 5 |
Correct |
82 ms |
2904 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
199 ms |
2904 KB |
Output is correct |
| 2 |
Correct |
220 ms |
2904 KB |
Output is correct |
| 3 |
Correct |
222 ms |
2904 KB |
Output is correct |
| 4 |
Correct |
208 ms |
2904 KB |
Output is correct |
| 5 |
Correct |
214 ms |
2904 KB |
Output is correct |
| 6 |
Correct |
219 ms |
2904 KB |
Output is correct |
| 7 |
Correct |
184 ms |
2904 KB |
Output is correct |
| 8 |
Correct |
227 ms |
2904 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
98 ms |
2904 KB |
Output is correct |
| 2 |
Correct |
203 ms |
2904 KB |
Output is correct |
| 3 |
Correct |
205 ms |
2904 KB |
Output is correct |
| 4 |
Correct |
144 ms |
2904 KB |
Output is correct |
| 5 |
Correct |
158 ms |
2904 KB |
Output is correct |
| 6 |
Correct |
143 ms |
2904 KB |
Output is correct |
| 7 |
Correct |
110 ms |
2904 KB |
Output is correct |
| 8 |
Correct |
182 ms |
2904 KB |
Output is correct |
| 9 |
Correct |
154 ms |
2904 KB |
Output is correct |
| 10 |
Correct |
172 ms |
2904 KB |
Output is correct |
| 11 |
Correct |
156 ms |
2904 KB |
Output is correct |
| 12 |
Correct |
185 ms |
2904 KB |
Output is correct |
| 13 |
Correct |
148 ms |
2904 KB |
Output is correct |
| 14 |
Correct |
197 ms |
2904 KB |
Output is correct |
| 15 |
Correct |
133 ms |
2904 KB |
Output is correct |
| 16 |
Correct |
198 ms |
2904 KB |
Output is correct |
| 17 |
Correct |
74 ms |
2904 KB |
Output is correct |
| 18 |
Correct |
171 ms |
2904 KB |
Output is correct |
| 19 |
Correct |
105 ms |
2904 KB |
Output is correct |
| 20 |
Correct |
175 ms |
2904 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
2904 KB |
Wrong Answer[2] |
| 2 |
Halted |
0 ms |
0 KB |
- |
