oj.uz

Submission #57731

# Submission time Handle Problem Language Result Execution time Memory
57731 2018-07-16T00:25:21 Z Benq ICC (CEOI16_icc) C++14
90 / 100
 218 ms 1304 KB 
#include "icc.h"

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
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;

template<int SZ> struct DSU {
    int par[SZ], sz[SZ];
    DSU() {
        F0R(i,SZ) par[i] = i, sz[i] = 1;
    }
    
    int get(int x) { // path compression
    	if (par[x] != x) par[x] = get(par[x]);
    	return par[x];
    }
    
    bool unite(int x, int y) { // union-by-rank
    	x = get(x), y = get(y);
    	if (x == y) return 0;
    	if (sz[x] < sz[y]) swap(x,y);
    	sz[x] += sz[y], par[y] = x;
    	return 1;
    }
};

DSU<101> D;
int N;
/*pi des;

int query(int size_a, int size_b, int a[], int b[]) {
    F0R(i,size_a) cout << a[i] << " ";
    cout << "| ";
    F0R(i,size_b) cout << b[i] << " ";
    cout << "|\n";
    F0R(i,size_a) F0R(j,size_b) {
        if (a[i] == des.f && b[j] == des.s) return 1;
        if (a[i] == des.s && b[j] == des.f) return 1;
    }
    return 0;
}*/

bool QUERY(vi a, vi b) {
    int A[sz(a)]; F0R(i,sz(a)) A[i] = a[i];
    int B[sz(b)]; F0R(i,sz(b)) B[i] = b[i];
    return query(sz(a),sz(b),A,B);
}

void ad(vi& a, vi b) { for (int i: b) a.pb(i); }

/*void setRoad(int a, int b) {
     cout << "AH " << a << " " << b << "\n";
     if (mp(a,b) == mp(3,1)) des = {4,2};
     else exit(0);
}*/

void bipartite(vi x, vi y) {
    while (1) {
        if (sz(x) < sz(y)) swap(x,y);
        if (sz(x) == 1) {
            D.unite(x[0],y[0]);
            setRoad(x[0],y[0]);
            return;
        }
        vi X = vi(x.begin(),x.begin()+sz(x)/2);
        if (QUERY(X,y)) x = X;
        else x = vi(x.begin()+sz(x)/2,x.end());
    }
}

void getBit(vector<vi> V) {
    int cur = 1;
    while (1) {
        vi a,b;
        F0R(i,sz(V)) {
            if (i&cur) ad(a,V[i]);
            else ad(b,V[i]);
        }
        if (QUERY(a,b)) {
            bipartite(a,b);
            return;
        }
        cur *= 2;
    }
}

void solve() {
    vi v[101];
    FOR(i,1,N+1) v[D.get(i)].pb(i);
    vector<vi> V;
    FOR(i,1,N+1) if (sz(v[i])) V.pb(v[i]);
    getBit(V);
}

void run(int n) {
    N = n;
    F0R(i,N-1) solve();
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 504 KB Ok! 94 queries used.
2 Correct 10 ms 744 KB Ok! 105 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 744 KB Ok! 548 queries used.
2 Correct 61 ms 772 KB Ok! 674 queries used.
3 Correct 55 ms 904 KB Ok! 675 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 1144 KB Ok! 1477 queries used.
2 Correct 218 ms 1144 KB Ok! 1659 queries used.
3 Correct 172 ms 1144 KB Ok! 1575 queries used.
4 Correct 154 ms 1144 KB Ok! 1515 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 1144 KB Ok! 1515 queries used.
2 Correct 194 ms 1144 KB Ok! 1552 queries used.
3 Correct 179 ms 1144 KB Ok! 1665 queries used.
4 Correct 141 ms 1172 KB Ok! 1551 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 1228 KB Ok! 1683 queries used.
2 Correct 170 ms 1276 KB Ok! 1684 queries used.
3 Correct 166 ms 1276 KB Ok! 1673 queries used.
4 Correct 176 ms 1296 KB Ok! 1633 queries used.
5 Correct 159 ms 1296 KB Ok! 1512 queries used.
6 Correct 152 ms 1304 KB Ok! 1568 queries used.

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 163 ms 1304 KB Too many queries! 1688 out of 1625
2 Halted 0 ms 0 KB -