oj.uz

답안 #72987

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
72987 2018-08-27T12:11:04 Z Benq Park (JOI17_park) C++14
67 / 100
 227 ms 2904 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;
}

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) {
    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,merge(bad,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);
    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;  }
    }
}

#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
0 / 10.0

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

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 87 ms 744 KB Output is correct
2 Correct 148 ms 748 KB Output is correct
3 Correct 136 ms 2904 KB Output is correct
4 Correct 90 ms 2904 KB Output is correct
5 Correct 82 ms 2904 KB Output is correct

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 199 ms 2904 KB Output is correct
2 Correct 220 ms 2904 KB Output is correct
3 Correct 222 ms 2904 KB Output is correct
4 Correct 208 ms 2904 KB Output is correct
5 Correct 214 ms 2904 KB Output is correct
6 Correct 219 ms 2904 KB Output is correct
7 Correct 184 ms 2904 KB Output is correct
8 Correct 227 ms 2904 KB Output is correct

Subtask #4
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 98 ms 2904 KB Output is correct
2 Correct 203 ms 2904 KB Output is correct
3 Correct 205 ms 2904 KB Output is correct
4 Correct 144 ms 2904 KB Output is correct
5 Correct 158 ms 2904 KB Output is correct
6 Correct 143 ms 2904 KB Output is correct
7 Correct 110 ms 2904 KB Output is correct
8 Correct 182 ms 2904 KB Output is correct
9 Correct 154 ms 2904 KB Output is correct
10 Correct 172 ms 2904 KB Output is correct
11 Correct 156 ms 2904 KB Output is correct
12 Correct 185 ms 2904 KB Output is correct
13 Correct 148 ms 2904 KB Output is correct
14 Correct 197 ms 2904 KB Output is correct
15 Correct 133 ms 2904 KB Output is correct
16 Correct 198 ms 2904 KB Output is correct
17 Correct 74 ms 2904 KB Output is correct
18 Correct 171 ms 2904 KB Output is correct
19 Correct 105 ms 2904 KB Output is correct
20 Correct 175 ms 2904 KB Output is correct

Subtask #5
0 / 23.0

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