oj.uz

답안 #549996

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
549996 2022-04-17T03:42:28 Z balbit Park (JOI17_park) C++14
67 / 100
 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

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 340 KB Wrong Answer[6]
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 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

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 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

Subtask #4
30.0 / 30.0

# 결과 실행 시간 메모리 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

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 124 ms 552 KB Wrong Answer[6]
2 Halted 0 ms 0 KB -