oj.uz

답안 #72805

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
72805 2018-08-27T02:27:02 Z Benq Park (JOI17_park) C++14
20 / 100
 238 ms 34336 KB 
#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;
}
void answer(int l, int r) {
    if (l > r) swap(l,r);
    Answer(l,r);
}
// END UTILITY 

bool inTree[1400];

vi divi(int l, int r) {
    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) {
    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,vi(cur.begin(),cur.begin()+mid))) hi = mid;
        else lo = mid+1;
    }
    return cur[lo-1];
}

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);
        return;
    }
    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) { cur.pb(i); inTree[i] = 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) {
			    cout << "BAD " << A << " " << B << "\n";
			    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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 13 ms 484 KB Output is correct
3 Correct 13 ms 536 KB Output is correct
4 Correct 13 ms 536 KB Output is correct
5 Correct 15 ms 592 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 804 KB Output is correct
2 Correct 106 ms 804 KB Output is correct
3 Correct 87 ms 2876 KB Output is correct
4 Correct 50 ms 2876 KB Output is correct
5 Correct 43 ms 2876 KB Output is correct

Subtask #3
0 / 27.0

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

Subtask #4
0 / 30.0

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

Subtask #5
0 / 23.0

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