Submission #72991

#	Time	Username	Problem	Language	Result	Execution time	Memory
72991		Benq	Park (JOI17_park)	C++14	100 / 100	266 ms	2848 KiB

park

#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, bool b = 1) {
    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,b?merge(bad,vi(cur.begin(),cur.begin()+mid)):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,0);
    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;  }
        //cout << "HI "; for (int i: cur) cout << i << " ";
        //cout << "\n";
    }
}

#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

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 27 / 27
• Subtask 4: 30 / 30
• Subtask 5: 23 / 23