oj.uz

Submission #549994

# Submission time Handle Problem Language Result Execution time Memory
549994 2022-04-17T03:40:21 Z balbit Park (JOI17_park) C++14
0 / 100
 2 ms 468 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 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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Wrong Answer[1]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 468 KB Wrong Answer[1]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 468 KB Wrong Answer[1]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Wrong Answer[1]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 468 KB Wrong Answer[1]
2 Halted 0 ms 0 KB -