| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 549996 |
2022-04-17T03:42:28 Z |
balbit |
Park (JOI17_park) |
C++14 |
|
147 ms |
2000 KB |
#ifndef BALBIT
#include "park.h"
#endif
#include <bits/stdc++.h>
//#define int ll
using namespace std;
#define ll long long
#define y1 zck_is_king
#define pii pair<ll, ll>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif
const int iinf = 1e9+10;
const ll inf = 1ll<<60;
const ll mod = 1e9+7 ;
const int maxn = 1500+5;
#ifdef BALBIT
vector<int> gra[maxn];
bool seen[maxn];
bool dfs(int v, int b, int Place[]) {
if (v == b) return 1;
seen[v] = 1;
for (int u : gra[v]) {
if (!seen[u] && Place[u]) {
if (dfs(u,b,Place)) return 1;
}
}
return 0;
}
bool Ask(int a, int b, int Place[]) {
assert(Place[a] && Place[b]);
memset(seen, 0, sizeof seen);
return dfs(a,b,Place);
}
void Answer(int a, int b) {
bug("answering ", a,b);
}
#endif // BALBIT
namespace {
vector<int> tree[maxn];
bool intree[maxn];
int n;
}
static int Place[1400];
bool ask(int a,int b,vector<int> v) {
if (a==b) return 1;
if (a > b) swap(a,b);
memset(Place, 0, sizeof Place);
for (int x : v) Place[x] = 1;
assert(Place[a] && Place[b]);
return Ask(a,b,Place);
}
void answer(int a, int b) {
Answer(min(a,b), max(a,b));
}
void addtree (int a, int b) {
bug("edge ", a,b);
answer(a,b);
tree[a].pb(b); tree[b].pb(a);
intree[a] = intree[b] = 1;
}
void build(int a, int b) {
assert(a!=b);
if (ask(a,b,{a,b})) {
addtree(a,b); return;
}
vector<int> can; // candidates
REP(i,n) {
if (i!=a && i!=b && !intree[i]) {
can.pb(i);
}
}
int l = 0, r = SZ(can); // the graph should be connected, so it'll find something?????
while (l!=r) {
int mid = (l+r)/2;
vector<int> go(can.begin(), can.begin() + mid);
go.pb(a); go.pb(b);
if (ask(a,b,go)) {
// maybe i can go lower
r = mid;
}else{
l = mid+1;
}
}
assert(l!=0); // otherwise they'd be connected!?
int ele = can[l-1];
build(a,ele);
build(ele,b);
}
void dfs(int v, int p, vector<int> &tnodes) {
tnodes.pb(v);
for (int u : tree[v]) {
if( u != p) {
dfs(u, v, tnodes);
}
}
}
void buildtree(){
intree[0] = 1;
for (int i = 1; i<n; ++i) {
if (!intree[i]) {
// find a person in the current tree to branch off of
vector<int> tnodes; // ok tnodes should be sorted by dfs order or depth... sorry
dfs(0, -1, tnodes);
vector<int> nottnodes;
REP(j,n) if (!intree[j]) nottnodes.pb(j);
int l = 1, r = SZ(tnodes);
while (l!=r) {
int mid = (l+r)/2;
vector<int> go (tnodes.begin(), tnodes.begin() + mid);
go.insert(go.end(), nottnodes.begin(), nottnodes.end());
if (ask(0, i, go)) {
// reachable... i can use fewer nodes
r = mid;
}else {
l = mid+1;
}
}
int a = tnodes[l-1];
bug(a, i);
build(a,i);
}
}
}
void Detect(int T, int N) {
n=N;
buildtree();
}
#ifdef BALBIT
signed main(){
IOS();
vector<pii> edges = {{0,4}, {0,2}, {1,2}, {1,3}, {2,5}, {4,6}, {4,7}};
REP(i, SZ(edges)) {
gra[edges[i].f].pb(edges[i].s);
gra[edges[i].s].pb(edges[i].f);
}
int N = SZ(edges)+1;
Detect(-1, N);
}
#endif
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Wrong Answer[6] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
41 ms |
652 KB |
Output is correct |
| 2 |
Correct |
131 ms |
716 KB |
Output is correct |
| 3 |
Correct |
96 ms |
2000 KB |
Output is correct |
| 4 |
Correct |
40 ms |
696 KB |
Output is correct |
| 5 |
Correct |
41 ms |
724 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
125 ms |
624 KB |
Output is correct |
| 2 |
Correct |
142 ms |
524 KB |
Output is correct |
| 3 |
Correct |
137 ms |
528 KB |
Output is correct |
| 4 |
Correct |
147 ms |
488 KB |
Output is correct |
| 5 |
Correct |
132 ms |
532 KB |
Output is correct |
| 6 |
Correct |
133 ms |
532 KB |
Output is correct |
| 7 |
Correct |
140 ms |
544 KB |
Output is correct |
| 8 |
Correct |
135 ms |
468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
58 ms |
508 KB |
Output is correct |
| 2 |
Correct |
124 ms |
584 KB |
Output is correct |
| 3 |
Correct |
127 ms |
584 KB |
Output is correct |
| 4 |
Correct |
91 ms |
612 KB |
Output is correct |
| 5 |
Correct |
116 ms |
644 KB |
Output is correct |
| 6 |
Correct |
91 ms |
684 KB |
Output is correct |
| 7 |
Correct |
62 ms |
668 KB |
Output is correct |
| 8 |
Correct |
119 ms |
600 KB |
Output is correct |
| 9 |
Correct |
92 ms |
588 KB |
Output is correct |
| 10 |
Correct |
122 ms |
664 KB |
Output is correct |
| 11 |
Correct |
126 ms |
684 KB |
Output is correct |
| 12 |
Correct |
123 ms |
636 KB |
Output is correct |
| 13 |
Correct |
70 ms |
632 KB |
Output is correct |
| 14 |
Correct |
132 ms |
684 KB |
Output is correct |
| 15 |
Correct |
69 ms |
628 KB |
Output is correct |
| 16 |
Correct |
138 ms |
520 KB |
Output is correct |
| 17 |
Correct |
40 ms |
724 KB |
Output is correct |
| 18 |
Correct |
124 ms |
648 KB |
Output is correct |
| 19 |
Correct |
69 ms |
668 KB |
Output is correct |
| 20 |
Correct |
116 ms |
600 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
124 ms |
552 KB |
Wrong Answer[6] |
| 2 |
Halted |
0 ms |
0 KB |
- |
