제출 #72783

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
72783		Benq	Park (JOI17_park)	C++14	20 / 100	141 ms	12208 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  7
#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];

bool ok(int a, int b, vi x) {
    if (a > b) swap(a,b);
    memset(Place,0,sizeof Place);
    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,{}); }

void divi(int l, int r) {
    if (checkEdge(l,r)) { Answer(min(l,r),max(l,r)); return; }
    vi tmp; 
    F0R(i,n) if (i != l && i != r) 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;
    }
    divi(l,tmp[lo-1]); divi(tmp[lo-1],r);
}

void Detect(int T, int _n) {
    n = _n;
    if (T == 1) {
        F0R(i,n) FOR(j,i+1,n) if (checkEdge(i,j)) Answer(i,j);
    }
    if (T == 2) {
        divi(0,n-1);
    }
}

#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;
	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[]) {
	visited[now] = 1;
	int i;
	for(i = 0 ; i < degree[now] ; i++) {
		if(visited[edge_list[now][i]] == 0 && Place[edge_list[now][i]] == 1) dfs(edge_list[now][i], Place);
	}
}
int Ask(int A, int B, int Place[]) {
	int i;
	Asktotal++;
	if(Asktotal>QMAX) WA(5);
	if(A < 0||A >= B||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);
	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;
	}
	Detect(T, N);
	if(Answertotal<M) WA(6);
	printf("Accepted\n");
	return 0;
}

#endif

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